graph-theory
这是 拟阵笔记 的一章。 上一篇是 对偶，下一篇是 平坦集与几何格。
Rank and closure
### Rank
Definition（Rank function）. The rank of $A\subseteq E$ is \[ r(A)=\max\{\lvert I\rvert: I\subseteq A,\ I\in\mathcal{I}\}, \] the size of any maximal independent subset of $A$. Homework 2 in the notes records that $(A,\mathcal{I}\cap 2^{A})$ is itself a matroid (the restriction $M|A$, written $M\setminus(E\setminus A)$ later); all its bases have the same size by , so the maximum is attained and is independent of the choice of basis. The rank of $M$ is $r(M)=r(E)$.
Proposition. The rank function satisfies, for all $X,Y\subseteq E$,
1. $0\le r(X)\le\lvert X\rvert$; 2. $X\subseteq Y$ implies $r(X)\le r(Y)$; 3. $r(X\cup Y)+r(X\cap Y)\le r(X)+r(Y)$ (submodularity).
*Proof.* (R1) and (R2) are immediate. For (R3), let $A$ be a basis of $X\cap Y$, and extend $A$ to a basis $B$ of $X\cup Y$. Write $B=A\sqcup C\sqcup D$ with $C\subseteq X\setminus Y$ and $D\subseteq Y\setminus X$ (elements of $B\setminus A$ lying in $X\cap Y$ cannot occur: they would enlarge the basis $A$ of $X\cap Y$). Then \[ r(X\cup Y)=\lvert B\rvert=\lvert A\rvert+\lvert C\rvert+\lvert D\rvert, r(X\cap Y)=\lvert A\rvert, \] while $A\cup C\subseteq X$ is independent so $r(X)\ge\lvert A\rvert+\lvert C\rvert$, and likewise $r(Y)\ge\lvert A\rvert+\lvert D\rvert$. Adding these inequalities gives (R3).
Lemma. If $r(X\cup\{y\})=r(X)$ for every $y\in Y$, then $r(X\cup Y)=r(X)$.
*Proof.* Induct on $\lvert Y\rvert$. The cases $\lvert Y\rvert\le 1$ are tautological. Write $Y=Y'\cup\{y\}$ with $\lvert Y'\rvert=n-1$. The inductive hypothesis gives $r(X\cup Y')=r(X)$. Submodularity then yields
$$ \begin{aligned} r(X\cup Y) &=r((X\cup Y')\cup(X\cup\{y\}))\\ &\le r(X\cup Y')+r(X\cup\{y\})-r(X) =r(X)+r(X)-r(X) =r(X), \end{aligned} $$
and the reverse inequality is (R2).
Theorem. A function $r\colon 2^{E}\to\mathbb{N}$ is the rank function of a matroid on $E$ if and only if it satisfies (R1)–(R3).
*Proof.* The forward direction is . Conversely, set $\mathcal{I}=\{I\subseteq E: r(I)=\lvert I\rvert\}$. We check that $(E,\mathcal{I})$ is a matroid whose rank function is the given $r$.
(I1): (R1) forces $r(\varnothing)=0=\lvert \varnothing\rvert$. (I2): if $I\subseteq J$ and $r(J)=\lvert J\rvert$, submodularity gives $r(I)+r(J\setminus I)\ge r(J)+r(\varnothing)=\lvert J\rvert$, while $r(J\setminus I)\le\lvert J\setminus I\rvert$, so $r(I)\ge\lvert I\rvert$. Combined with (R1) we get $r(I)=\lvert I\rvert$.
For (I3), let $I,J\in\mathcal{I}$ with $\lvert I\rvert<\lvert J\rvert$, and suppose $I\cup\{j\}\notin\mathcal{I}$ for every $j\in J\setminus I$. Then $r(I\cup\{j\})<\lvert I\rvert+1$. But $r(I\cup\{j\})\ge r(I)=\lvert I\rvert$, so $r(I\cup\{j\})=r(I)$. yields $r(I\cup J)=r(I)=\lvert I\rvert<\lvert J\rvert=r(J)\le r(I\cup J)$, a contradiction.
Finally, the rank of this matroid recovers $r$. Let $X\subseteq E$ and let $I\subseteq X$ be a maximal member of $\mathcal{I}$. Then $r(I)=\lvert I\rvert$. For each $y\in X\setminus I$ the set $I\cup\{y\}$ is not independent, so $r(I\cup\{y\})=\lvert I\rvert=r(I)$. gives $r(X)=r(I)=\lvert I\rvert$, which is the matroid rank of $X$.
### Closure
Definition（Closure）. The closure of $X\subseteq E$ is \[ \overline(X)=\{x\in E:\ r(X\cup\{x\})=r(X)\}. \]
This is “span, for matroids”. It satisfies the Kuratowski closure axioms, plus the MacLane–Steinitz exchange axiom:
1. $X\subseteq\overline(X)$; 2. $X\subseteq Y$ implies $\overline(X)\subseteq\overline(Y)$; 3. $\overline(\overline(X))=\overline(X)$; 4. if $x\in\overline(X\cup\{y\})$ and $x\notin\overline(X)$, then $y\in\overline(X\cup\{x\})$.
Analogues: topological closure, linear span, the vertices generating a connected subgraph.
Lemma. For any $X\subseteq E$ and $x\in E$, either $r(X\cup\{x\})=r(X)$ or $r(X\cup\{x\})=r(X)+1$.
*Proof.* Let $B$ be a basis of $X$. Then either $B$ or $B\cup\{x\}$ is a basis of $X\cup\{x\}$.
*Proof.* (CL1) is together with $r(X\cup\{x\})=r(X)$ when $x\in X$.
(CL2). Let $X\subseteq Y$ and $x\in\overline(X)$, so $r(X\cup\{x\})=r(X)$. Let $B$ be a basis of $X$; then $B$ is also a basis of $X\cup\{x\}$, i.e.\ $B\cup\{x\}$ is dependent. Extend $B$ to a basis $C$ of $Y\cup\{x\}$. Then $x\notin C$ (else $B\cup\{x\}$ would be independent), so $C\subseteq Y$ and $r(Y)\ge\lvert C\rvert=r(Y\cup\{x\})$. Thus $r(Y)=r(Y\cup\{x\})$ and $x\in\overline(Y)$.
(CL3). Always $X\subseteq\overline(X)\subseteq\overline(\overline(X))$. If $x\in\overline(\overline(X))$ then $r(\overline(X)\cup\{x\})=r(\overline(X))$. The local rank lemma gives $r(\overline(X))=r(X)$, because $r(X\cup\{y\})=r(X)$ for every $y\in\overline(X)$. Hence $r(X\cup\{x\})=r(X)$ and $x\in\overline(X)$.
(CL4). Suppose $y\in\overline(X\cup\{x\})$ and $y\notin\overline(X)$. Then $r(X\cup\{x,y\})=r(X\cup\{x\})$ and $r(X\cup\{y\})=r(X)+1$. Therefore \[ r(X\cup\{x,y\})=r(X\cup\{x\})\le r(X)+1=r(X\cup\{y\}), \] so $r(X\cup\{x\})=r(X\cup\{y\})$ and $x\in\overline(X\cup\{y\})$.
Theorem. A map $\overline\colon 2^{E}\to 2^{E}$ is the closure operator of a matroid on $E$ if and only if it satisfies (CL1)–(CL4).
*Proof.* Given $\overline$, declare $I$ independent if $x\notin\overline(I\setminus\{x\})$ for every $x\in I$.
(I1) is vacuous. (I2): if $I\subseteq J$ with $J$ independent and $x\in I$, then $I\setminus\{x\}\subseteq J\setminus\{x\}$, so $\overline(I\setminus\{x\})\subseteq\overline(J\setminus\{x\})$ by (CL2), hence $x\notin\overline(J\setminus\{x\})$ forces $x\notin\overline(I\setminus\{x\})$.
> *Filled in.* If $I$ is independent and $e\notin I$, then $I\cup\{e\}$ is dependent if > and only if $e\in\overline(I)$. > > If $e\in\overline(I)$, then $e\in\overline((I\cup\{e\})\setminus\{e\})$, so > $I\cup\{e\}$ is dependent. Conversely, if $I\cup\{e\}$ is dependent then > some $x\in I\cup\{e\}$ satisfies $x\in\overline((I\cup\{e\})\setminus\{x\})$. > If $x=e$ we are done. If $x\in I$, then > $x\in\overline((I\setminus\{x\})\cup\{e\})$ while > $x\notin\overline(I\setminus\{x\})$ (since $I$ is independent). (CL4) yields > $e\in\overline((I\setminus\{x\})\cup\{x\})=\overline(I)$.
For (I3), let $I,J\in\mathcal{I}$ with $\lvert I\rvert<\lvert J\rvert$, and suppose $I\cup\{j\}$ is dependent for every $j\in J\setminus I$. The lemma gives $J\setminus I\subseteq\overline(I)$, hence $J\subseteq\overline(I)$ by (CL1). Independence of $J$ says that each $y\in J$ satisfies $y\notin\overline(J\setminus\{y\})$. But $J\setminus\{y\}\subseteq\overline(I)$, so $\overline(J\setminus\{y\})\subseteq\overline(\overline(I))=\overline(I)$ by (CL2)–(CL3), and therefore $y\notin\overline(I)$. This forces $J=\varnothing$, contradicting $\lvert J\rvert>\lvert I\rvert$.
The closure of the resulting matroid is the given operator: $e$ is in the matroid closure of $X$ if and only if $e$ does not enlarge a basis of $X$, if and only if $e\in\overline(X)$ by the lemma (applied after extending a basis of $X$ using (CL3)).
Note. A closure operator with the exchange property (CL4) is a matroid (combinatorial independence). A closure operator with the anti-exchange property \[ x\in\overline(X\cup\{y\})\setminus\overline(X) \Longrightarrow y\notin\overline(X\cup\{x\}) \] is a convex geometry (combinatorial convexity). The convex hull is the motivating example of anti-exchange.
> *Filled in.* Concretely: if $x$ lies in the convex hull of $X\cup\{y\}$ but not of > $X$, then $y$ cannot lie in the convex hull of $X\cup\{x\}$ (else $x$ and > $y$ would be interchangeable, as in a linear dependence). Three collinear > points in the plane give a convex geometry that is not a matroid, because > the middle point is in the hull of the outer two, violating exchange.
> *Supplement.* Two more families of sets, dual to independent sets and circuits. A set > $X$ is spanning if $r(X)=r(E)$, equivalently $\overline(X)=E$. The > minimal spanning sets are exactly the bases. A hyperplane is a > maximal non-spanning set, equivalently a flat of rank $r(M)-1$; the > hyperplanes of $M$ are the complements of the cocircuits. Thus: > independent $\leftrightarrow$ co-spanning, circuit $\leftrightarrow$ > cocircuit, spanning $\leftrightarrow$ co-independent, hyperplane > $\leftrightarrow$ complement of a circuit of $M^{\ast}$. > > A set $I$ is independent if and only if $r(I)=\lvert I\rvert$, and $X$ is > spanning if and only if $r(X)=r(E)$. Combining both: $B$ is a basis if > and only if $r(B)=\lvert B\rvert=r(E)$.