= Basis of a matroid
{title2=$B$}
= Bases of a matroid
{synonym}
= Matroid basis
{synonym}
= Matroid bases
{synonym}
A <matroid basis> is a <matroid independent set> that is a <maximal element> under inclusion of <subsets>: no additional element of the <ground set> can be admitted. Maximum <cardinality> means having the largest size among all <matroid independent sets>. Maximality tests whether this particular selection can grow; maximum size compares it with every selection. In a <matroid> the two conditions coincide, so all <matroid bases> have a common size. They need not have equal weight. <Matroid optimization by Michel Goemans>[Michel X. Goemans, Matroid optimization, section 5.1, p. 1, maximal independent sets and bases]{ref}
\b[Proof outline.] If a maximal <matroid independent set> $B$ were smaller than another <matroid independent set> $J$, the <matroid independence axioms> would admit an element of $J\setminus B$, contradicting maximality. Finiteness allows every <matroid independent set> to grow to a <matroid basis> by successive admissible additions. In a general <independence system>, maximal selections can have different sizes, as in the <hereditary nonmatroid greedy obstruction>.
Back to article page
