graph-theory
这是 拟阵笔记 的一章。 上一篇是 子阵，下一篇是 代数拟阵。
Forbidden minors and representability
Closure under minors and duality is useful because it yields characterisations by excluded minors.
| | minors | duality | | — | — | — | | graphic | yes | no | | linear | yes | yes | | transversal | no | no | | gammoid | yes | yes |
### Graphic matroids
Example. To test whether a list $\mathcal{C}$ is the circuit list of a graphic matroid, pass to a minor. If $\mathcal{C}=\{1279,1289,13456,1379,2345,2567,2789\}$, then \[ M\setminus\{3,4,5,6\}/9 \] has circuits $\{127,128,178,278\}$, i.e.\ is $U_{2,4}$, which is not graphic.
Proposition. $U_{m,n}$ is graphic only for the values $(m,n)\in\{(0,n),(1,n),(n-1,n),(n,n)\}\cup\{(2,n): n\le 3\}$. In particular $U_{2,4}$ is not graphic.
*Proof.* Deletion and contraction of uniform matroids stay uniform: $U_{m,n}/e\cong U_{m-1,n-1}$ and $U_{m,n}\setminus e\cong U_{m,n-1}$. Starting from $U_{m,n}$ with $2\le m\le n-2$ one reaches $U_{2,4}$ as a minor, and $U_{2,4}$ is the cycle matroid of no graph (it would be a $2$-connected graph on $4$ edges with every $2$-set independent, hence $K_4$ minus two edges, which has a $3$-circuit).
Other non-graphic examples: $M(K_5)^{\ast}$, $M(K_{3,3})^{\ast}$, and the Fano matroid $F_7$ and its dual.
Theorem（Tutte, 1959）. A matroid is graphic if and only if it has no minor isomorphic to $U_{2,4}$, $M(K_5)^{\ast}$, $M(K_{3,3})^{\ast}$, $F_7$, or $F_7^{\ast}$.
The proof is omitted on the board (it occupies Oxley, Chapter 13); the five matroids are exhibited as minors, but the converse—that every non-graphic matroid has one of them—is a long structural argument. These five are the forbidden minors for graphic matroids.
### The Fano matroid
The Fano matroid $F_7$ has ground set $\{a,b,c,d,e,f,g\}$ and circuits the seven $3$-point lines \[ \{abc, cde, efa, agd, bge, cgf, bdf\}. \] It is the matroid of $\mathrm{PG}(2,2)$: the seven nonzero vectors in $\F_2^3$.
Proposition. $F_7$ is not representable over $\mathbb{R}$ (nor over any field of characteristic not $2$).
*Proof.* Suppose it is represented in $\mathbb{R}^3$. We may take $a=(1,0,0)$, $c=(0,1,0)$, $e=(0,0,1)$, and $g=(x,y,z)$ with $xyz\neq 0$. The three lines through $g$ force $d\parallel (0,y,z)$, $f\parallel (x,0,z)$, $b\parallel (x,y,0)$. The remaining line $\{b,d,f\}$ then gives a linear dependence $\alpha d+\beta f+\gamma b=0$ whose three coordinates read $x(\beta+\gamma)=y(\alpha+\gamma)=z(\alpha+\beta)=0$. Thus $\alpha+\beta=\beta+\gamma=\gamma+\alpha=0$, so $2\alpha=0$. Over $\mathbb{R}$ this forces $\alpha=0$ and then $\beta=\gamma=0$, a contradiction. Hence $F_7$ is not $\mathbb{R}$-representable; the same computation in characteristic not $2$ gives $2=0$, likewise a contradiction.
Corollary. $F_7^{\ast}$ is not representable over $\mathbb{R}$.
> *Filled in.* If $F_7^{\ast}$ had an $\mathbb{R}$-representation, then > would give an $\mathbb{R}$-representation of its dual $F_7$, contradicting the > proposition.
### Representability over finite fields
Theorem（Tutte, 1958）. A matroid is representable over $\mathrm{GF}(2)$ if and only if it has no $U_{2,4}$ minor.
Theorem（Bixby 1979 / Seymour 1979）. A matroid is representable over $\mathrm{GF}(3)$ if and only if it has no minor among $U_{2,5}$, $U_{3,5}$, $F_7$, $F_7^{\ast}$.
Theorem（Tutte, 1958）. A matroid is representable over *every* field if and only if it has no minor among $U_{2,4}$, $F_7$, $F_7^{\ast}$. Such matroids are called regular.
For each finite field $\mathrm{GF}(q)$ there is a finite list of excluded minors for $\mathrm{GF}(q)$-representability.
Rota's conjecture is now a theorem: Geelen, Gerards, and Whittle announced a proof in 2014. The $\mathrm{GF}(4)$ case (seven excluded minors) is due to Geelen, Gerards, and Kapoor (2000). Over $\mathbb{R}$, or any characteristic-zero field, there are infinitely many excluded minors (Lazarson, 1958). Which uniform matroids $U_{r,n}$ are representable over $\mathrm{GF}(q)$ remains a lively question (the MDS conjecture).
### Non-linear matroids
$F_7$ is not representable in characteristic not $2$; $F_7^{\ast}$ is not representable in characteristic $2$. Consequently:
Proposition. The direct sum $F_7\oplus F_7^{\ast}$ is not linear over any field: a representation would restrict to $F_7$ (forcing $\mathrm{char}=2$) and to $F_7^{\ast}$ (forcing $\mathrm{char}\neq 2$).
A configuration $v_1,\ldots,v_n$ is affinely independent if $\sum a_i v_i=0$ with $\sum a_i=0$ forces all $a_i=0$ (two points distinct, three non-collinear, four non-coplanar, \ldots).
Proposition. A loopless matroid is linear if and only if it is the affine matroid of some point configuration. (Pass to the linear matroid of the homogenised vectors $(1,v_i)$.)
The non-Pappus, non-Desargues, and V\'amos matroids arise by taking the indicated projective configurations and deleting a collinearity circuit; they are matroids, but not representable.
Theorem（Desargues）. If triangles $ABC$ and $A'B'C'$ are perspective from a point $P$, then the points $R=BC\cap B'C'$, $S=AC\cap A'C'$, $T=AB\cap A'B'$ are collinear.
*Proof.* Place the two triangles in different planes meeting in a line. Then $AB$ and $A'B'$ meet on that line, and likewise for the other pairs, so $R,S,T$ lie on the line of intersection of the two planes.
The Desargues matroid is the affine matroid of $\{A,B,C,A',B',C',P,R,S,T\}$; it is isomorphic to $M(K_5)$. The non-Desargues matroid is the same except that $\{R,S,T\}$ is declared independent. It is a matroid (direct verification of (I3), or the standard “relax a circuit-hyperplane” construction) but not representable, because any linear representation would force Desargues' theorem.
> *Supplement.* Two special cases of representability have names. A matroid is > binary if it is representable over $\mathrm{GF}(2)$, > equivalently (Tutte) if it has no $U_{2,4}$ minor; graphic matroids are > binary, which is why $U_{2,4}$ appears among Tutte's five forbidden > minors for graphicness. A matroid is regular if it is > representable over every field, equivalently if it has a totally > unimodular representation over $\mathbb{R}$ (every square submatrix has > determinant in $\{0,\pm 1\}$). Regular matroids include all graphic and > cographic matroids; Seymour's decomposition theorem (1980) builds every > regular matroid from graphic ones, cographic ones, and a single > $10$-element sporadic $R_{10}$ by $3$-sums. > > Whitney's $2$-isomorphism theorem (the project “when is $M(G)\cong M(H)$?” > on the board) says that two $2$-connected graphs have isomorphic cycle > matroids if and only if one is obtained from the other by a sequence of > Whitney twists: cut along a $2$-vertex separator and reverse one side. > > Pappus's theorem is the companion of Desargues: given two lines with > points $A,B,C$ and $A',B',C'$ respectively, the three points > $AB'\cap A'B$, $AC'\cap A'C$, $BC'\cap B'C$ are collinear. Relaxing that > collinearity circuit produces the non-Pappus matroid drawn above, which > is not representable over any field (a coordinatisation would force > Pappus). The same circuit-hyperplane relaxation—declaring > independent a set that is simultaneously a circuit and a hyperplane, and > taking the resulting new bases—is the standard way to manufacture > non-representable matroids from representable ones, and is how > non-Desargues arises from $M(K_5)$.