graph-theory
这是 拟阵笔记 的一章。 上一篇是 平坦集与几何格，下一篇是 可表示性。
Minors
Vector spaces have subspaces; graphs have subgraphs. Matroids have minors.
### Rank on the Boolean lattice
One way to think about a matroid is as a labelling of $2^{E}$ by integers. For the triangle $G$ with edges $\{1,2,3,4\}$ as drawn (bases $\{12,13,14,23,24\}$):
A rank function is a labelling of $2^{E}$ such that along any covering $X\subset X\cup\{e\}$ the label stays or increases by $1$, and every “parallelogram” $X,X\cup\{a\},X\cup\{b\},X\cup\{a,b\}$ is submodular. Subcubes inherit these properties, so they are matroids: this is deletion and contraction.
### Deletion and contraction
Definition（Deletion）. For $T\subseteq E$, the deletion $M\setminus T$ (restriction $M|(E\setminus T)$) has ground set $E\setminus T$ and rank $r_{M\setminus T}(X)=r_M(X)$ for $X\subseteq E\setminus T$.
Definition（Contraction）. The contraction $M/T$ has ground set $E\setminus T$ and rank \[ r_{M/T}(X)=r_M(X\cup T)-r_M(T). \]
Proposition. If $S\cap T=\varnothing$ then
$$ \begin{aligned} (M\setminus S)\setminus T &= M\setminus(S\cup T) =(M\setminus T)\setminus S,\\ (M/S)/T &= M/(S\cup T) =(M/T)/S,\\ (M/S)\setminus T &= (M\setminus T)/S. \end{aligned} $$
Thus deletion and contraction commute: a string of deletions and contractions may be rewritten in any order. For instance $M/2\setminus 59/6/7\setminus 8 = M/267\setminus 589$.
Definition（Minor）. A minor of $M$ is a matroid $M/S\setminus T$ with $S\cap T=\varnothing$.
Proposition（Duality interchanges deletion and contraction）. \[ (M/T)^{\ast}=M^{\ast}\setminus T, (M\setminus T)^{\ast}=M^{\ast}/T. \]
Proposition. The dual rank is $r_{M^{\ast}}(X)=\lvert X\rvert-r_M(E)+r_M(E\setminus X)$.
> *Filled in.* This is Homework 4 in the notes; the board “flip the Boolean lattice” > picture is unlabeled. In symbols: a basis of $M^{\ast}$ contained in $X$ > is $X\setminus B$, where $B$ is a basis of $M$ that meets $E\setminus X$ > in as many elements as possible, i.e.\ $\lvert B\cap(E\setminus X)\rvert=r(E\setminus X)$. > Then > \[ > r_{M^{\ast}}(X) > =\lvert X\rvert-(r(M)-r(E\setminus X)) > =\lvert X\rvert-r(M)+r(E\setminus X). > \]
Proposition. $$ \begin{aligned} \mathcal{I}(M\setminus T) &=\{I\subseteq E\setminus T:\ I\in\mathcal{I}(M)\},\\ \mathcal{I}(M/T) &=\{I\subseteq E\setminus T:\ I\cup B_T\in\mathcal{I}(M)\}, \end{aligned} $$
where $B_T$ is any basis of $T$. Circuits: $\mathcal{C}(M\setminus T)=\{C\in\mathcal{C}(M): C\cap T=\varnothing\}$, while $\mathcal{C}(M/T)$ consists of the inclusion-minimal sets among $\{C\setminus T: C\in\mathcal{C}(M)\}$. Closure in the contraction: $\cl_{M/T}(X)=\cl_M(X\cup T)\setminus T$.
### Graphic minors
Graph deletion of an edge $e$ is ordinary deletion of $e$. Graph contraction of $e=i_1i_2$ identifies $i_1$ with $i_2$.
Proposition. $M(G\setminus e)=M(G)\setminus e$ and $M(G/e)=M(G)/e$. Consequently every minor of a graphic matroid is graphic.
*Proof.* An edge-set $I\not\ni e$ is acyclic in $G\setminus e$ if and only if it is acyclic in $G$. If $e$ is not a loop, $I$ is independent in $M(G)/e$ if and only if $I\cup\{e\}$ is acyclic in $G$, if and only if $I$ is acyclic in $G/e$.
### Linear minors
Deleting a vector $e$ from a configuration $E\subseteq V$ yields $E\setminus\{e\}$ in $V$. Contracting $e$ is the configuration $\pi(E\setminus\{e\})$ in $e^{\perp}$, where $\pi\colon V\to e^{\perp}$ is orthogonal projection.
Proposition. $M(E\setminus e)=M(E)\setminus e$ and $M(E/e)=M(E)/e$. Every minor of a linear matroid is linear.
*Proof.* The deletion claim is immediate. For contraction: $I$ is independent in $M(E)/e$ if and only if $I\cup\{e\}$ is linearly independent, if and only if there is no linear relation among $\pi(I)$, because a relation $\sum c_i v_i+c e=0$ projects to $\sum c_i\pi(v_i)=0$, and conversely a relation among the projections lifts by an element of $\ker\pi=\langle e\rangle$.
### Transversal minors and gammoids
Is every minor of a transversal matroid transversal? Deletion is: if $e$ “decides not to marry”, erase $e$ from the bipartite graph.
Contraction is not: forcing $e$ to be matched can produce a non-transversal matroid.
Example. A transversal matroid $M=M(G)$ with a non-transversal contraction $M/a$. The original drawing is cramped; the intended configuration is: the circuits of $M$ include $\{b_1,b_2\}$, $\{c_1,c_2\}$, $\{d_1,d_2\}$ and $\{a,b_i\}$, $\{a,c_j\}$, $\{a,d_k\}$. After contracting $a$ one obtains circuits $\{b_1,b_2\}$, $\{c_1,c_2\}$, $\{d_1,d_2\}$ together with all mixed triples $b_ic_jd_k$, which no bipartite presentation realises (any presentation would have to match the three pairs from three distinct men, yet also match a mixed triple, forcing a Hall violator).
Graphic and linear matroids are closed under minors and duality. Transversal matroids are closed under deletion and dualise to cotransversal matroids, but are not closed under contraction.
Definition（Gammoid）. A gammoid is a contraction of a transversal matroid.
Proposition. Gammoids are closed under minors and duality, and they form the smallest such class containing the transversal matroids.
*Proof.* Let $M=T/B$ with $T$ transversal. Contraction: $M/A=T/(A\cup B)$, a gammoid. Deletion: $M\setminus A=(T\setminus A)/B$, and $T\setminus A$ is transversal. Duality: $T=U\setminus C$ for a cotransversal $U$ (Ingleton–Piff), so $M^{\ast}=(U\setminus C/B)^{\ast}=U^{\ast}/C\setminus B$ with $U^{\ast}$ transversal, hence a gammoid.
> *Supplement.* The Tutte polynomial of the greedy chapter is most cleanly computed by > the same two operations. If $e$ is neither a loop nor a coloop, > \[ > T_M(x,y)=T_{M\setminus e}(x,y)+T_{M/e}(x,y); > \] > a coloop contributes a factor $x$ and a loop a factor $y$. In particular > $T_M(1,1)$ is the number of bases, $T_M(2,0)$ is (for a graphic matroid) > the number of acyclic orientations, and $T_M(0,2)$ counts totally cyclic > orientations. The same recurrence computes the chromatic polynomial of a > graph as $\chi_G(\lambda)=(-1)^{r(M(G))}\lambda^{\kappa(G)}T_{M(G)}(1-\lambda,0)$. > > A useful numerical check: in the running example $r(M)=3$, there are five > bases, a unique loop $f$, and a unique coloop $a$. Deleting $f$ and > contracting $a$ leaves a $4$-element rank-$2$ matroid (a triangle with one > edge doubled), whose Tutte polynomial is $x^{2}+x+y+xy+y^{2}$; multiplying > by the loop and coloop factors $y$ and $x$ recovers $T_M$. > > A minor of $M$ can always be realised as a restriction of a contraction > of a restriction (the scum theorem): after simplifying, every > minor appears as a restriction of $M/F$ for some flat $F$. In particular > it is enough, when testing a minor-closed property, to look at > restrictions of contractions. > > Series and parallel connections of matroids generalise identifying > endpoints of graphs. The cycle matroids of series-parallel graphs are > precisely the graphic matroids with no $M(K_4)$ minor; they are the > building blocks of regular matroids of small connectivity.