Matroid

combinatorics computation

Definition

Matroid

A matroid is a pair $M=(E,\mathcal{I})$ where $E$ is a ground set, a finite non-empty set, and $\mathcal{I}\subseteq 2^E$ is a family of independent sets satisfying three axioms:

1. Non-emptiness: $\varnothing \in \mathcal{I}$.
2. Heredity: If $X\subseteq Y$ and $Y\in \mathcal{I}$, then $X\in \mathcal{I}$.
3. Exchangeability: If $X,Y\in \mathcal{I}$ and $|X|<|Y|$, then there exists $e\in Y\setminus X$ such that $X\cup \{e\}\in \mathcal{I}$.

A set $X\subseteq E$ is a dependent set if $X\notin \mathcal{I}$. A maximal independent set is a basis of $M$.

The diagram is a Hasse diagram for the partial order $\subseteq$ on the power set $2^E$.

Ground Set

Definition

Ground Set (Matroid)

In a matroid $M=(E,\mathcal{I})$, the ground set is the finite non-empty set $E$ whose subsets are classified as independent or dependent by the family $\mathcal{I}$. It is the universe of objects the matroid reasons about — the raw elements from which independent sets are drawn.

The family $\mathcal{I}\subseteq 2^E$ is the collection of subsets of $E$ declared independent. It is the rule that decides, for each subset of the ground set, whether it counts as independent or not. The matroid structure is determined not by $E$ alone, but by the choice of $\mathcal{I}$ on it: the same ground set can carry different matroids.

Link to original

Family

Definition

Family

A family of elements of a set $X$ indexed by an index set $I$ is a function

$$f:I\to X.$$

Writing $x_i=f(i)$, the family is denoted

$$(x_i{)}_{i\in I}.$$

The index set $I$ labels the elements; the codomain $X$ says where they live. The function viewpoint lets the same element appear for several indices, so a family need not be a set: it carries indexing and repetition that a set does not.

Link to original

Axioms

Non-emptiness

Definition

Non-emptiness (Matroid)

The non-emptiness axiom for a matroid $M=(E,\mathcal{I})$ states that

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

Equivalently, at least one subset of the ground set, namely the empty set, is an independent set.

Link to original

Heredity

Definition

Heredity (Matroid)

The heredity axiom (also called the monotonicity property) for a matroid $M=(E,\mathcal{I})$ states that

$$X\subseteq Y,Y\in \mathcal{I}⟹X\in \mathcal{I}.$$

Every subset of an independent set is independent.

Link to original

Exchangeability

Definition

Exchangeability (Matroid)

The exchangeability axiom (also called the exchange property) for a matroid $M=(E,\mathcal{I})$ states that

$$X,Y\in \mathcal{I},|X|<|Y|⟹\exists e\in Y\setminus X:X\cup \{e\}\in \mathcal{I}.$$

A smaller independent set can always be extended by some element of a larger independent set while staying independent.

Link to original

Interpretation

A matroid captures the abstract notion of “independence” common to several settings. It strips away whether the objects are vectors, edges, or anything else, and keeps only the combinatorial shape of which subsets count as independent.

The three axioms isolate exactly the behaviour needed for a greedy algorithm to work. Matroids are the shape behind greedy.

Rank

Definition

Rank (Matroid)

The rank of a matroid $\mathcal{M}$ is the cardinality of any basis of $\mathcal{M}$.

Link to original

Examples

Vector Matroid

Definition

Vector Matroid

A vector matroid (also called a linear matroid) is a matroid $M=(E,\mathcal{I})$ whose ground set $E$ is a finite set of vectors in a vector space $V$ over a field $F$, and whose independent sets are the linearly independent subsets of $E$:

$$\mathcal{I}=\{X\subseteq E\mid X\text{ is linearly independent}\}.$$

Link to original

Graphic Matroid

Definition

Graphic Matroid

A graphic matroid (also called a cycle matroid) is a matroid $M=(E,\mathcal{I})$ whose ground set $E$ is the edge set of an undirected graph $G=(V,E)$, and whose independent sets are the acyclic edge sets, that is, the forests:

$$\mathcal{I}=\{X\subseteq E\mid (V,X)\text{ is acyclic}\}.$$

Link to original

Uniform Matroid

Definition

Uniform Matroid

A matroid $M=(E,\mathcal{I})$ over an $n$-element ground set $E$ is a uniform matroid $U_{k,n}$ if the family of independent sets is

$$\mathcal{I}=\{X\subseteq E\mid |X|\le k\}$$

for some constant $k\in \{0,1,\dots ,n\}$. A subset is independent exactly when its size is at most $k$.

Link to original