基

这是 拟阵笔记 的一章。 上一篇是 独立集，下一篇是 贪心算法。

Bases

Definition（Basis）. A basis of a matroid is a maximal independent set: an independent set not properly contained in a larger independent set.

In the running example \[ \mathcal{B}=\{abc, abd, abe, acd, ace\}. \] This is a shorter description of $M$, because the independent sets are precisely the subsets of bases.

Proposition. All bases of a matroid have the same cardinality.

*Proof.* Suppose $B_1,B_2$ are bases with $\lvert B_1\rvert<\lvert B_2\rvert$. By (I3) there is $b\in B_2\setminus B_1$ with $B_1\cup\{b\}$ independent, contradicting maximality of $B_1$.

The common cardinality is the rank $r(M)$ of $M$.

Corollary. Every independent set is contained in a basis.

*Proof.* Let $I$ be independent. Among independent sets containing $I$, take one of maximal cardinality; it is a basis by , else (I3) would enlarge it.

Example. In the matching picture one cannot match all six right-hand vertices. But every matchable set extends to a matchable set of size $r(M)=3$. For instance $\{a,d\}$ extends (e.g.\ to $\{a,b,d\}$).

Example（Linear）. In a linear matroid a basis is a basis of the span, and equicardinality is dimension.

Example（Graphic）. If $G$ is connected, the bases of $M(G)$ are the spanning trees of $G$ (connected, acyclic, spanning subgraphs). If $G$ is disconnected, they are the spanning forests (a spanning tree of each component). That these all have the same number of edges is the matroidal content of “$n-c$ edges in a forest with $c$ components”.

Example（Transversal）. Let $S$ be a finite set with distinguished subsets $S_1,\ldots,S_n$. A transversal (or system of distinct representatives) is a subset $T=\{a_1,\ldots,a_n\}\subseteq S$ with $a_i\in S_i$ for each $i$. The bases of the corresponding transversal matroid are precisely the transversals.

In the running example $S=\{a,b,c,d,e,f\}$ with \[ S_1=\{a\}, S_2=\{a,b,c\}, S_3=\{a,b,c,d,e\}, \] and the transversals are exactly the five bases listed above.

### Basis axioms

Proposition. Let $E$ be finite and $\mathcal{B}\subseteq 2^{E}$. Then $\mathcal{B}$ is the collection of bases of a matroid on $E$ if and only if

1. $\mathcal{B}\neq\varnothing$; 2. if $A,B\in\mathcal{B}$ and $a\in A\setminus B$, then there exists $b\in B\setminus A$ such that $(A\setminus\{a\})\cup\{b\}\in\mathcal{B}$.

Axiom (B2) is basis exchange.

*Proof.* Independent sets exist ((I1)), so maximal ones exist: (B1). For (B2), take bases $A,B$ and $a\in A\setminus B$. Then $A\setminus\{a\}$ is independent of size $r(M)-1$, while $B$ is independent of size $r(M)$. By (I3) there is $b\in B\setminus(A\setminus\{a\})$ with $(A\setminus\{a\})\cup\{b\}$ independent, hence a basis. This $b$ cannot lie in $A$ (else we would recover $A$, but $a\notin B$ so $b\neq a$ forces $b\in B\setminus A$).

*Proof.* Let $\mathcal{B}$ satisfy (B1)–(B2). Write \[ \mathcal{I}=\{I\subseteq E:\ I\subseteq B\text{ for some }B\in\mathcal{B}\}. \]

*Step 1.* All members of $\mathcal{B}$ have the same size.

Take $B\in\mathcal{B}$ of minimal cardinality. We claim every $A\in\mathcal{B}$ has $\lvert A\rvert=\lvert B\rvert$. Induct on $\lvert A\setminus B\rvert$. If $\lvert A\setminus B\rvert=0$ then $A\subseteq B$; minimality forces $A=B$. If $\lvert A\setminus B\rvert=k\ge 1$, pick $a\in A\setminus B$. By (B2) there is $b\in B\setminus A$ with $A'=(A\setminus\{a\})\cup\{b\}\in\mathcal{B}$. Then \[ \lvert A'\setminus B\rvert=\lvert A\setminus B\rvert-1, \] so the inductive hypothesis gives $\lvert A'\rvert=\lvert B\rvert$. But $\lvert A'\rvert=\lvert A\rvert$, hence $\lvert A\rvert=\lvert B\rvert$.

Write $r$ for this common size.

*Step 2.* $(E,\mathcal{I})$ is a matroid.

(I1): $\varnothing\subseteq B$ for any $B\in\mathcal{B}$. (I2) is immediate from the definition of $\mathcal{I}$.

For (I3), let $I,J\in\mathcal{I}$ with $\lvert I\rvert<\lvert J\rvert$. We induct on $r-\lvert J\rvert$.

*Initial case* $r-\lvert J\rvert=0$: then $J$ is a basis. Let $A$ be a basis containing $I$, and write \[ X=A\cap J\setminus I, Y=A\setminus J. \] The scans label two subsets $B,C$ of $A$ without defining them consistently; the three cases below are the intended partition.

• If $X\neq\varnothing$, pick $a\in X$. Then $a\in J\setminus I$ and $I\cup\{a\}\subseteq A$, so $I\cup\{a\}\in\mathcal{I}$.
• If $Y\neq\varnothing$, pick $a\in Y\subseteq A\setminus J$. By (B2) there is $j\in J\setminus A$ with $A'=(A\setminus\{a\})\cup\{j\}\in\mathcal{B}$. Then $I\cup\{j\}\subseteq A'$ (since $a\notin I$: otherwise $a\in I\subseteq J$, contradicting $a\in Y$) and $j\in J\setminus I$.
• If $X=Y=\varnothing$, then $A\subseteq J$. But $\lvert A\rvert=\lvert J\rvert=r$, so $A=J$ and therefore $I\subseteq J$ with $\lvert I\rvert<\lvert J\rvert=r=\lvert A\rvert$, contradicting that $A$ was a basis containing $I$ unless $I$ can still be augmented—in fact $A=J$ and $I\subsetneq A$, so $A\setminus I\neq\varnothing$ forces $X\neq\varnothing$. This case cannot occur.

*Inductive step.* Suppose the claim holds whenever $r-\lvert J'\rvert=k-1$, and now $r-\lvert J\rvert=k\ge 1$. Let $I\subseteq A\in\mathcal{B}$ and $J\subseteq B\in\mathcal{B}$. Applying the initial-case argument to the pair $(I,B)$ (here $B$ is a basis) produces $b\in B\setminus I$ with $I\cup\{b\}\in\mathcal{I}$.

If $b\in J$ we are done. If $b\notin J$, then $J\cup\{b\}\subseteq B$, so $J\cup\{b\}\in\mathcal{I}$. Now $I\cup\{b\}$ and $J\cup\{b\}$ are independent with \[ \lvert I\cup\{b\}\rvert<\lvert J\cup\{b\}\rvert, r-\lvert J\cup\{b\}\rvert=k-1. \] The inductive hypothesis supplies $c\in (J\cup\{b\})\setminus(I\cup\{b\})$ with $I\cup\{b,c\}\in\mathcal{I}$, hence $c\in J\setminus I$ and $I\cup\{c\}\in\mathcal{I}$.

Definition（Matroid via bases）. Equivalently, a matroid is a pair $(E,\mathcal{B})$ with $\mathcal{B}$ satisfying (B1)–(B2). One passes between the two presentations by \[ \mathcal{B}=\{\text{maximal members of }\mathcal{I}\}, \mathcal{I}=\{\text{subsets of members of }\mathcal{B}\}. \]

### A philosophical aside

Two axiom systems describe the same objects: (I1)–(I3) for independence, and (B1)–(B2) for bases. Proving they are equivalent takes work. The deeper difficulty is to find good axiom systems.

(I1)–(I3) is a good system for independence: it applies at once to linear algebra, graphs, matchings (and, later, Dyck paths, \ldots), and it is precisely the class of simplicial complexes on which greedy works. (B1)–(B2) is a good system for bases: it is weak enough that independence implies it, and strong enough to recover independence.

> *Supplement.* Direct sums are the disjoint-union operation on matroids. If $M$ and $N$ > have disjoint ground sets, the direct sum $M\oplus N$ has ground > set $E(M)\sqcup E(N)$ and independent sets $I\sqcup J$ with $I$ independent > in $M$ and $J$ independent in $N$. Rank, circuits, and flats all act > componentwise: $r_{M\oplus N}(X)=r_M(X\cap E(M))+r_N(X\cap E(N))$. A > matroid is connected if it is not a direct sum of two nonempty > matroids; equivalently, every pair of elements lies in a common circuit. > The running example is connected (after deleting the loop $f$ it remains > connected). Direct sum is the operation that later produces the > non-representable matroid $F_7\oplus F_7^{\ast}$.

上一篇：独立集。下一篇：贪心算法。回到 目录。