graph-theory
这是 拟阵笔记 的一章。 上一篇是 贪心算法，下一篇是 对偶。
Circuits
We have described matroids by bases and by independent sets. What about dependent sets?
Relabel the running example as $E=\{1,2,3,4,5,6\}$ via $a\mapsto 1,\ldots,f\mapsto 6$, so \[ \mathcal{B}=\{123,124,125,134,135\}. \] The collection $\mathcal{D}$ of dependent sets is long ($\{6\}$, every set containing $6$, $\{4,5\}$, $\{2,3,4\}$, $\{2,3,5\}$, $\{2,4,5\}$, $\{3,4,5\}$, \ldots). It is enough to list the minimal dependent sets: \[ \mathcal{C}=\{6, 45, 234, 235\}. \]
Definition（Circuit）. A circuit of a matroid is a minimal dependent set.
Circuits determine the matroid: a set is dependent if and only if it contains a circuit, and independent if and only if it contains none.
### Circuit axioms
1. $\varnothing$ is not a circuit. 2. No circuit properly contains another circuit. 3. (elimination) If $C_1,C_2$ are distinct circuits and $x\in C_1\cap C_2$, then there is a circuit $C_3\subseteq (C_1\cup C_2)\setminus\{x\}$.
In graphs, (C3) is the usual cycle-exchange picture: two cycles sharing an edge yield a third cycle in the symmetric difference.
Theorem. Let $E$ be finite and $\mathcal{C}\subseteq 2^{E}$. Then $\mathcal{C}$ is the collection of circuits of a matroid on $E$ if and only if it satisfies (C1)–(C3).
*Proof.* Let $\mathcal{C}$ be the circuits of a matroid. (C1) holds because $\varnothing$ is independent. (C2) is minimality.
For (C3), suppose $C_1,C_2$ are circuits, $x\in C_1\cap C_2$, and (for a contradiction) $(C_1\cup C_2)\setminus\{x\}$ is independent. Since $C_1\not\subseteq C_2$ there is $y\in C_1\setminus C_2$. Then $C_1\setminus\{y\}$ is independent, as is $(C_1\cup C_2)\setminus\{x\}$. Repeated augmentation of $C_1\setminus\{y\}$ by elements of $C_2$ produces, after finitely many steps, the conclusion that $C_1\cup C_2\setminus\{y\}$ is independent. But $C_2\subseteq C_1\cup C_2\setminus\{y\}$, so $C_2$ is independent, a contradiction.
> *Filled in.* Define $\mathcal{I}=\{I\subseteq E:\ \text{no member of $\mathcal{C}$ is contained in $I$}\}$. > (I1) is (C1); (I2) is immediate. For (I3) we induct on > $\lvert I\setminus J\rvert$. Let $I,J$ be $\mathcal{C}$-independent with $\lvert I\rvert<\lvert J\rvert$. > > If $I\setminus J=\varnothing$ then $I\subseteq J$, so any $j\in J\setminus I$ > augments $I$. Now suppose $e\in I\setminus J$. The set $I\setminus\{e\}$ is > independent of smaller excess over $J$, so induction supplies > $f\in J\setminus I$ with $(I\setminus\{e\})\cup\{f\}$ independent. > > If $I\cup\{f\}$ is independent we are done. Otherwise the unique circuit > $C\subseteq I\cup\{f\}$ contains both $e$ and $f$ (neither $I$ nor > $(I\setminus\{e\})\cup\{f\}$ contains a circuit). Set > $I':=(I\setminus\{e\})\cup\{f\}$. Then $\lvert I'\rvert=\lvert I\rvert<\lvert J\rvert$ and > $\lvert I'\setminus J\rvert=\lvert I\setminus J\rvert-1$, so induction supplies > $g\in J\setminus I'$ with $I'\cup\{g\}$ independent. > > The element $g$ also augments $I$. If not, a circuit $C'\subseteq I\cup\{g\}$ > contains $g$ and $e$ (since $I'\cup\{g\}$ is independent). Then $e\in C\cap C'$, > so (C3) yields a circuit contained in $(C\cup C')\setminus\{e\} > \subseteq I'\cup\{g\}$, contradicting independence of $I'\cup\{g\}$. > Finally $g\in J\setminus I$, as required. > > Thus $(E,\mathcal{I})$ is a matroid whose circuits are exactly $\mathcal{C}$.
> *Supplement.* The weak elimination axiom (C3) has a stronger form, equally > characteristic of matroids. Strong circuit elimination: if > $C_1,C_2$ are distinct circuits, $e\in C_1\cap C_2$, and > $f\in C_1\setminus C_2$, then some circuit $C_3$ satisfies > $f\in C_3\subseteq (C_1\cup C_2)\setminus\{e\}$. (In graphs: the third > cycle through a prescribed edge of $C_1\setminus C_2$.) One also has > uniqueness of the circuit in $I\cup\{e\}$ whenever $I$ is independent and > $I\cup\{e\}$ is dependent; this is the fundamental-circuit lemma of the > next section. > > A set $X$ is spanning if and only if it meets every cocircuit (circuit of > $M^{\ast}$). Dually, $X$ is independent if and only if it meets no > circuit. This is the first instance of the independence / spanning > duality that organises the rest of the notes. > > Given a basis $B$, the fundamental circuits $C(e,B)$ for $e\notin B$ > already determine $M$: a set is dependent if and only if it contains one > of these circuits or fails to be contained in a basis obtained by the > usual exchanges. Equivalently, the fundamental cocircuits > $C^{\ast}(b,E\setminus B)$ for $b\in B$ determine the dual, hence $M$.