Basis (Matroid)

discrete-mathematics combinatorics

Definition

Basis (Matroid)

Let $M=(E,\mathcal{I})$ be a matroid. A basis of $M$ is a maximal independent set: a set $B\in \mathcal{I}$ such that

$$B\subseteq E\text{is basis of}\mathcal{M}⟺\forall e\in E\setminus B:B\cup \{e\}\notin \mathcal{I}$$

No independent set properly contains a basis.

All bases have the same size

All bases have the same size

By exchangeability, any two bases of a matroid have the same cardinality. This common size is the rank of the matroid.

Proof

If two bases $X,Y$ had $|X|<|Y|$, exchangeability would supply some $e\in Y\setminus X$ with $X\cup \{e\}$ independent, contradicting the maximality of $X$.