Basis Family (Matroid)

discrete-mathematics combinatorics

Definition

Basis Family

A matroid can also be defined directly through its bases, without first specifying the independent sets. The collection of bases itself satisfies three axioms.

Let $E$ be a finite set and $\mathcal{B}$ a family of subsets of $E$ satisfying three axioms:

1. Non-emptiness: $\mathcal{B}\ne \varnothing$.
2. Equal cardinality: For all $B_1,B_2\in \mathcal{B}$, it holds that $|B_1|=|B_2|$.
3. Basis exchange: For all $B_1,B_2\in \mathcal{B}$ and all $x\in B_1\setminus B_2$, there exists $y\in B_2\setminus B_1$ such that $(B_1\setminus \{x\})\cup \{y\}\in \mathcal{B}$.

Any such family $\mathcal{B}$ is the set of bases of a unique matroid on $E$, whose independent sets are exactly the subsets of elements of $\mathcal{B}$.

Relation to the independent-set axioms

The basis-family axioms are equivalent to the independent-set axioms. Given a matroid $M=(E,\mathcal{I})$, its bases are the maximal independent sets, and they satisfy non-emptiness, equal cardinality, and basis exchange. Conversely, given a basis family $\mathcal{B}$, the corresponding independence family is

$$\mathcal{I}=\{X\subseteq E\mid X\subseteq B\text{ for some }B\in \mathcal{B}\}.$$

Axiom equal cardinality corresponds to the consequence of exchangeability that all bases have the same size. Axiom basis exchange is a basis-level form of exchange: instead of extending a smaller independent set, it swaps an element between two equal-size bases.

Examples

Uniform matroid $U_{2,4}$

Let $E=\{1,2,3,4\}$ and

$$\mathcal{B}=\{B\mid B\subseteq E\wedge |B|=2\}.$$

The basis family is the collection of all $2$-element subsets of $E$. It satisfies non-emptiness, since $\mathcal{B}$ is non-empty, since every basis has size $2$, and (B3) since swapping any element of one $2$-set for an element of another yields another $2$-set.