Independent Set (Matroid)

discrete-mathematics combinatorics

Definition

Independent Set (Matroid)

Let $M=(E,\mathcal{I})$ be a matroid. A set $X\subseteq E$ is an independent set of $M$ if

$$X\in \mathcal{I}.$$

The family $\mathcal{I}$ is the collection of all independent sets, fixed by the three matroid axioms: non-emptiness, heredity, and exchangeability.

Example

What $\mathcal{I}$ contains

Let the ground set be

$$E=\{a,b,c\}.$$

Suppose we want the independent sets to be exactly the subsets of size at most $2$. Then the independence family is

$$\mathcal{I}=\{\varnothing ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\}\}.$$

Here $\mathcal{I}$ is not one independent set. It is the full list of all sets that count as independent.

For example,

$$\{a,b\}\in \mathcal{I},$$

so $\{a,b\}$ is independent. But

$$\{a,b,c\}\notin \mathcal{I},$$

so $\{a,b,c\}$ is dependent.

This is the uniform matroid $U_{2,3}$: independence means “choose at most two elements”.

The notation $M=(E,\mathcal{I})$ therefore separates two levels:

Symbol	Meaning
$E$	the available elements
$X\subseteq E$	one candidate set of elements
$\mathcal{I}\subseteq 2^E$	the family of all candidate sets that are allowed

Thus writing $X\in \mathcal{I}$ means: the particular subset $X$ is one of the allowed independent subsets.