Ch.8: Matroid minors

Chapter 8 of the book "Matroids: A Geometric Introduction" by Gary Gordon and Jennifer McNulty (2012) 8.1. Excluded minors and the Scum Theorem 8.2. Binary matroids 8.3. Summary of excluded minor results

71 flashcards · Mathematics · by lakesare

Part of Textbooks › Matroids: A Geometric Introduction (Gordon, McNulty) · 9 courses

1. [Excluded minors and the Scum Theorem] What is a minor of a matroid MMM on the ground set EEE ?

   A matroid M/A−BM/A - BM/A−B : contract the elements of AAA and delete the elements of BBB , for disjoint A,B⊆EA, B \subseteq EA,B⊆E . The order of the deletions and contractions does not matter.Example: F7−/e−{b,d}F_7^-/e - \{b, d\}F7−​/e−{b,d} is a minor of the non-Fano plane F7−F_7^-F7−​ (contract eee , delete bbb and ddd ).

2. [Excluded minors and the Scum Theorem] When the book forms a minor M/A−BM/A - BM/A−B , which conditions does it put on AAA and BBB ?

   AAA is independent in MMM , and BBB contains no isthmus of M/AM/AM/A . So no loop is ever contracted and no isthmus is ever deleted.Example: in F7−F_7^-F7−​ , contracting {b,d,f}\{b, d, f\}{b,d,f} is not allowed: bdfbdfbdf is a line, so after contracting bbb and ddd the point fff is a loop.

3. [Excluded minors and the Scum Theorem] How do you get the four-point line U2,4U_{2,4}U2,4​ as a minor of this matroid, the non-Fano plane F7−F_7^-F7−​ ?

   Contract eee , then delete bbb and ddd : F7−/e−{b,d}≅U2,4\ F_7^-/e - \{b, d\} \cong U_{2,4} F7−​/e−{b,d}≅U2,4​ . r(F7−)=3r(F_7^-) = 3r(F7−​)=3 and r(U2,4)=2r(U_{2,4}) = 2r(U2,4​)=2 , and contraction lowers the rank, so exactly one of the three removed points is contracted and two are deleted. F7−/eF_7^-/eF7−​/e : rank 2, with double points ababab and cdcdcd . Deleting one point of each double point leaves four points on a line.

4. [Excluded minors and the Scum Theorem] F7−F_7^-F7−​ (non-Fano plane): 7 points, three-point lines abe,acf,adg,bdf,bcg,cdeabe, acf, adg, bdf, bcg, cdeabe,acf,adg,bdf,bcg,cde ( efgefgefg is not a line).Why is F7−/eF_7^-/eF7−​/e a rank-2 matroid whose only multiple points are the double points ababab and cdcdcd ?

   abeabeabe and cdecdecde are the only three-point lines through eee , so {a,b}\{a, b\}{a,b} and {c,d}\{c, d\}{c,d} are the only dependent 2-sets of F7−/eF_7^-/eF7−​/e . The independent sets of F7−/eF_7^-/eF7−​/e are all subsets of {a,b,c,d,f,g}\{a, b, c, d, f, g\}{a,b,c,d,f,g} of size at most 2 except {a,b}\{a, b\}{a,b} and {c,d}\{c, d\}{c,d} .

5. [Excluded minors and the Scum Theorem] F7−F_7^-F7−​ (non-Fano plane): 7 points, three-point lines abe,acf,adg,bdf,bcg,cdeabe, acf, adg, bdf, bcg, cdeabe,acf,adg,bdf,bcg,cde ( efgefgefg is not a line).How many U2,4U_{2,4}U2,4​ minors does F7−F_7^-F7−​ have (contract one point, delete two)?

   12=3⋅2⋅2\boldsymbol{12 = 3 \cdot 2 \cdot 2}12=3⋅2⋅2 Contract eee , fff or ggg (the points on exactly two three-point lines), then delete one point from each of the two double points.Example: contracting ddd gives no U2,4U_{2,4}U2,4​ : ddd lies on three three-point lines ( adg,bdf,cdeadg, bdf, cdeadg,bdf,cde ), so F7−/dF_7^-/dF7−​/d has three double points and simplifies to U2,3U_{2,3}U2,3​ .

6. [Excluded minors and the Scum Theorem] F7−F_7^-F7−​ (non-Fano plane): 7 points, three-point lines abe,acf,adg,bdf,bcg,cdeabe, acf, adg, bdf, bcg, cdeabe,acf,adg,bdf,bcg,cde ( efgefgefg is not a line).How many atoms and how many hyperplanes does the geometric lattice of flats of F7−F_7^-F7−​ have?

   7 atoms (the points) and 9 hyperplanes (six three-point lines and the three two-point lines ef,eg,fgef, eg, fgef,eg,fg ).

7. [Excluded minors and the Scum Theorem] Theorem 8.2 (Scum Theorem) NNN is a minor of MMM (ground set EEE ), and AAA is the set of points contracted to create NNN . Then the geometric lattice of NNN is isomorphic to … ?

   The upper interval [A‾,E][\overline{A}, E][A,E] in the geometric lattice of MMM ( A‾\overline{A}A = closure of AAA ). Precisely: the flats of M/AM/AM/A are the sets F−AF - AF−A for the flats F⊇A‾F \supseteq \overline{A}F⊇A of MMM . Deleting points afterwards keeps this lattice only when the deleted points are extra points of multiple points, as in passing to the simplification. Example: for F7−/eF_7^-/eF7−​/e the interval [e,E][e, E][e,E] has the four atoms abe,cde,ef,egabe, cde, ef, egabe,cde,…

8. [Excluded minors and the Scum Theorem] Why is the Scum Theorem called that?

   The lattice of a minor is an upper interval [F,E][F, E][F,E] , i.e. it is at the top of the lattice of MMM , as scum is at the top of a pond.

9. [Excluded minors and the Scum Theorem] What is the simplification si(M)si(M)si(M) of a matroid MMM ?

   Delete all loops of MMM and replace each multiple point by a single point. Example: si(F7−/e)=U2,4si(F_7^-/e) = U_{2,4}si(F7−​/e)=U2,4​ (the double points ababab and cdcdcd become single points).

10. [Excluded minors and the Scum Theorem] For S⊆ES \subseteq ES⊆E , what is the restriction (submatroid) M∣SM|_SM∣S​ ?

    The matroid on SSS whose independent sets are the independent sets of MMM contained in SSS . Everything outside SSS is ignored.Example: F7−∣{a,b,d,f}F_7^-|_{\{a, b, d, f\}}F7−​∣{a,b,d,f}​ is the line bdfbdfbdf and the point aaa off it:

11. [Excluded minors and the Scum Theorem] Proposition 8.3 MMM is a matroid on EEE , S⊆ES \subseteq ES⊆E and r(M∣S)=r(M)r(M|_S) = r(M)r(M∣S​)=r(M) . Then M∣S= ?M|_S = \; ?M∣S​=?

    M−(E−S)\boldsymbol{M - (E - S)}M−(E−S) Full rank means no isthmus is deleted (the book contracts isthmuses, it does not delete them).Example: F7−∣{a,b,d,f}=F7−−{c,e,g}F_7^-|_{\{a, b, d, f\}} = F_7^- - \{c, e, g\}F7−​∣{a,b,d,f}​=F7−​−{c,e,g} , both of rank 3.

12. [Excluded minors and the Scum Theorem] Why is the simplification si(M)si(M)si(M) a restriction of MMM , and of which form?

    si(M)=M∣S=M−(E−S)si(M) = M|_S = M - (E - S)si(M)=M∣S​=M−(E−S) , with SSS one point from each multiple point (no loops). r(si(M))=r(M)r(si(M)) = r(M)r(si(M))=r(M) , so the full-rank restriction is a deletion.Example: si(F7−/e)=(F7−/e)−{b,d}si(F_7^-/e) = (F_7^-/e) - \{b, d\}si(F7−​/e)=(F7−​/e)−{b,d} , with S={a,c,f,g}S = \{a, c, f, g\}S={a,c,f,g} .

13. [Excluded minors and the Scum Theorem] Theorem 8.6. For S⊆ES \subseteq ES⊆E , how is the restriction M∣SM|_SM∣S​ obtained by deletion and contraction?

    M∣S=(M−A)/B\boldsymbol{M|_S = (M - A)/B}M∣S​=(M−A)/B with A∪B=E−SA \cup B = E - SA∪B=E−S , A∩B=∅A \cap B = \emptysetA∩B=∅ and ∣B∣=r(M)−r(M∣S)|B| = r(M) - r(M|_S)∣B∣=r(M)−r(M∣S​) . Example: F7−∣{b,d,f}=(F7−−{c,e,g})/aF_7^-|_{\{b, d, f\}} = (F_7^- - \{c, e, g\})/aF7−​∣{b,d,f}​=(F7−​−{c,e,g})/a : in F7−−{c,e,g}F_7^- - \{c, e, g\}F7−​−{c,e,g} the point aaa is an isthmus, and ∣B∣=3−2=1|B| = 3 - 2 = 1∣B∣=3−2=1 .

14. [Excluded minors and the Scum Theorem] Is every restriction of MMM a minor of MMM ? Is every minor a restriction?

    Every restriction is a minor; not every minor is a restriction. Example: U2,4U_{2,4}U2,4​ is a minor of F7−F_7^-F7−​ but no restriction of F7−F_7^-F7−​ is a four-point line: every line (rank 2 flat) of F7−F_7^-F7−​ has 2 or 3 points.

15. [Excluded minors and the Scum Theorem] Proposition 8.7. MMM and M∗M^*M∗ are dual matroids. NNN is a minor of MMM if and only if … ?

    N∗N^*N∗ is a minor of M∗M^*M∗ . (M/A−B)∗=M∗/B−A(M/A - B)^* = M^*/B - A(M/A−B)∗=M∗/B−A : deletion and contraction swap under duality, and so do loops and isthmuses.Example: U2,4U_{2,4}U2,4​ is a minor of F7−F_7^-F7−​ , so U2,4∗=U2,4U_{2,4}^* = U_{2,4}U2,4∗​=U2,4​ is a minor of (F7−)∗(F_7^-)^*(F7−​)∗ .

16. [Excluded minors and the Scum Theorem] What form does an excluded minor characterization of a class of matroids have?

    MMM is in the class if and only if MMM has no minor isomorphic to N1,…,NkN_1, \dots, N_kN1​,…,Nk​ . N1,…,NkN_1, \dots, N_kN1​,…,Nk​ are the excluded (forbidden) minors. The class is e.g. binary, regular or graphic matroids.Example: MMM is binary if and only if MMM has no minor isomorphic to U2,4U_{2,4}U2,4​ .

17. [Excluded minors and the Scum Theorem] Proposition 8.8. A matroid MMM is a Boolean algebra (every subset independent) if and only if … ?

    MMM has no loop as a minor. Example: U2,3U_{2,3}U2,3​ is not a Boolean algebra: contracting aaa in the circuit {a,b,c}\{a, b, c\}{a,b,c} makes bbb and ccc parallel, and contracting bbb then makes ccc a loop.

18. [Excluded minors and the Scum Theorem] A matroid is a Boolean algebra if every subset is independent.Why does a matroid MMM that is not a Boolean algebra have a loop as a minor?

    MMM has a circuit C={e1,…,ek}C = \{e_1, \dots, e_k\}C={e1​,…,ek​} ; restrict to CCC and contract the independent set {e2,…,ek}\{e_2, \dots, e_k\}{e2​,…,ek​} : e1e_1e1​ becomes a loop. Conversely, in a Boolean algebra every point is an isthmus, so every minor is formed by contraction alone and consists of isthmuses.

19. [Excluded minors and the Scum Theorem] Proposition 8.9. Which single minor is excluded for the class of uniform matroids?

    U1,1⊕U0,1\boldsymbol{U_{1,1} \oplus U_{0,1}}U1,1​⊕U0,1​ : the two-point matroid made of an isthmus and a loop. Example: F7−∣{a,b,d,f}F_7^-|_{\{a, b, d, f\}}F7−​∣{a,b,d,f}​ is not uniform; contracting bbb and ddd makes fff a loop ( bdfbdfbdf is a line) while aaa is an isthmus.

20. [Excluded minors and the Scum Theorem] When is a class M\mathcal{M}M of matroids hereditary?

    M\mathcal{M}M is closed under deletion and contraction, i.e. every minor of a matroid in M\mathcal{M}M is in M\mathcal{M}M . Example: graphic matroids, and the matroids representable over a field F\mathbb{F}F , form hereditary classes.Example: the matroids on exactly 10 elements do not: a deletion has 9 elements.

21. [Excluded minors and the Scum Theorem] M\mathcal{M}M is a hereditary class. When is a matroid MMM an excluded (forbidden) minor for M\mathcal{M}M ?

    M∉MM \notin \mathcal{M}M∈/M , but every proper minor of MMM is in M\mathcal{M}M . So an excluded minor is minimal among the matroids outside M\mathcal{M}M .Example: U2,4U_{2,4}U2,4​ for binary matroids: U2,4U_{2,4}U2,4​ is not binary, but its deletions U2,3U_{2,3}U2,3​ , contractions U1,3U_{1,3}U1,3​ and all smaller minors are.

22. [Excluded minors and the Scum Theorem] Theorem 8.11 (Tutte). MMM is graphic if and only if MMM has no minor isomorphic to … ?

    U2,4, F7, F7∗, M(K5)∗, M(K3,3)∗\boldsymbol{U_{2,4}, \ F_7, \ F_7^*, \ M(K_5)^*, \ M(K_{3,3})^*}U2,4​, F7​, F7∗​, M(K5​)∗, M(K3,3​)∗ Four-point line, Fano plane, its dual, and the duals of the cycle matroids of K5K_5K5​ and K3,3K_{3,3}K3,3​ .

23. [Excluded minors and the Scum Theorem] Tutte: MMM is graphic if and only if MMM has no minor isomorphic to U2,4,F7,F7∗,M(K5)∗,M(K3,3)∗U_{2,4}, F_7, F_7^*, M(K_5)^*, M(K_{3,3})^*U2,4​,F7​,F7∗​,M(K5​)∗,M(K3,3​)∗ .Which part of the proof is hard?

    Showing the list is complete: every non-graphic matroid has one of the five as a minor. That the five are not graphic and that all their proper minors are graphic is easy.

24. [Binary matroids] What is a binary matroid?

    A matroid representable over F2={0,1}\mathbb{F}_2 = \{0, 1\}F2​={0,1} : the column dependences of a 0/1 matrix, computed modulo 2. Example: U2,3U_{2,3}U2,3​ is binary, given by the columns (1,0),(0,1),(1,1)(1, 0), (0, 1), (1, 1)(1,0),(0,1),(1,1) ; their sum is (0,0)(0, 0)(0,0) mod 2.

25. [Binary matroids] Write the vertex–edge incidence matrix AGA_GAG​ of this graph GGG .

    AGA_GAG​ : abcde111010201100310101400011\begin{array}{c|ccccc} & a & b & c & d & e \\ \hline 1 & 1 & 1 & 0 & 1 & 0 \\ 2 & 0 & 1 & 1 & 0 & 0 \\ 3 & 1 & 0 & 1 & 0 & 1 \\ 4 & 0 & 0 & 0 & 1 & 1 \end{array}1234​a1010​b1100​c0110​d1001​e0011​​ Rows are vertices, columns are edges; aij=1a_{ij} = 1aij​=1 if vertex iii is incident with edge jjj , else 0.

26. [Binary matroids] Vertex–edge incidence matrix of a graph GGG with 4 vertices and edges a=13,b=12,c=23,d=14,e=34a = 13, b = 12, c = 23, d = 14, e = 34a=13,b=12,c=23,d=14,e=34 : abcde111010201100310101400011\begin{array}{c|ccccc} & a & b & c & d & e \\ \hline 1 & 1 & 1 & 0 & 1 & 0 \\ 2 & 0 & 1 & 1 & 0 & 0 \\ 3 & 1 & 0 & 1 & 0 & 1 \\ 4 & 0 & 0 & 0 & 1 & 1 \end{array}1234​a1010​b1100​c0110​d1001​e0011​​ What is its rank over F2\mathbb{F}_2F2​ , and why?

    3: row 4 is the sum of rows 1, 2, 3 modulo 2. Each column has exactly two 1's, so the sum of all rows is 0 mod 2. Rank 3 = 4 vertices minus 1 component, the rank of M(G)M(G)M(G) .

27. [Binary matroids] Vertex–edge incidence matrix of a graph GGG with 4 vertices and edges a=13,b=12,c=23,d=14,e=34a = 13, b = 12, c = 23, d = 14, e = 34a=13,b=12,c=23,d=14,e=34 : abcde111010201100310101400011\begin{array}{c|ccccc} & a & b & c & d & e \\ \hline 1 & 1 & 1 & 0 & 1 & 0 \\ 2 & 0 & 1 & 1 & 0 & 0 \\ 3 & 1 & 0 & 1 & 0 & 1 \\ 4 & 0 & 0 & 0 & 1 & 1 \end{array}1234​a1010​b1100​c0110​d1001​e0011​​ What are the circuits of M(G)M(G)M(G) , and why are their columns dependent over F2\mathbb{F}_2…

    abcabcabc , adeadeade , bcdebcdebcde ; in their columns every row has zero or two 1's, so the columns sum to 0 mod 2. Example: a+b+c=(1,0,1,0)+(1,1,0,0)+(0,1,1,0)=(0,0,0,0)a + b + c = (1,0,1,0) + (1,1,0,0) + (0,1,1,0) = (0,0,0,0)a+b+c=(1,0,1,0)+(1,1,0,0)+(0,1,1,0)=(0,0,0,0) .

28. [Binary matroids] Theorem 8.13. Which class of matroids is contained in the binary matroids, with which representation?

    Graphic matroids are binary: M(G)M(G)M(G) is represented over F2\mathbb{F}_2F2​ by the vertex–edge incidence matrix AGA_GAG​ . Example: the triangle abcabcabc gives three columns of AGA_GAG​ with two 1's in each of its three vertex rows, summing to 0.

29. [Binary matroids] Representing M(G)M(G)M(G) over F2\mathbb{F}_2F2​ by the vertex–edge incidence matrix AGA_GAG​ of GGG .Which column does a loop of GGG give?

    The zero column, so the loop is a loop of the binary matroid too. The vertex of the loop gets entry 2≡0(mod2)2 \equiv 0 \pmod 22≡0(mod2) .

30. [Binary matroids] AGA_GAG​ is the vertex–edge incidence matrix of a graph GGG , over F2\mathbb{F}_2F2​ .Why do the columns of a cycle C={c1,…,cm}C = \{c_1, \dots, c_m\}C={c1​,…,cm​} of GGG form a circuit of M(AG)M(A_G)M(AG​) ?

    Every vertex of the cycle meets two edges of CCC : columns sum to 0. Without one column, row reduction gives an identity. So the columns of CCC are dependent, and every proper subset is independent.Ordered along the cycle, the columns have 1's on the diagonal, just below it, and in the top right corner.

31. [Binary matroids] AGA_GAG​ is the vertex–edge incidence matrix of a graph GGG , over F2\mathbb{F}_2F2​ , and CCC is a circuit of M(AG)M(A_G)M(AG​) ; ACA_CAC​ is the submatrix of the columns of CCC .How does the proof find a cycle of GGG among the edges of CCC ?

    Walk alternately along a column to its second 1 (other vertex) and along a row to another 1 (another edge of CCC ), until a row repeats. Every column of ACA_CAC​ has two 1's and every row an even number, so the walk can always continue. The cycle found is all of CCC : a cycle inside CCC is dependent, and a circuit has no dependent proper subset.

32. [Binary matroids] In the Fano plane F7F_7F7​ , C={a,b,e}C = \{a, b, e\}C={a,b,e} and C∗={b,d,e,g}C^* = \{b, d, e, g\}C∗={b,d,e,g} . Why is C∗C^*C∗ a cocircuit, and what is ∣C∩C∗∣|C \cap C^*|∣C∩C∗∣ ?

    C∗C^*C∗ is the complement of the line acfacfacf (a hyperplane); ∣C∩C∗∣=∣{b,e}∣=2|C \cap C^*| = |\{b, e\}| = 2∣C∩C∗∣=∣{b,e}∣=2 . In F7F_7F7​ , ∣C∩C∗∣|C \cap C^*|∣C∩C∗∣ is even for every circuit CCC and cocircuit C∗C^*C∗ .

33. [Binary matroids] In the Fano plane F7F_7F7​ , what is the symmetric difference of the circuits C1={e,f,g}C_1 = \{e, f, g\}C1​={e,f,g} and C2={a,d,e,f}C_2 = \{a, d, e, f\}C2​={a,d,e,f} ?

    {a,d,g}\boldsymbol{\{a, d, g\}}{a,d,g} , a circuit (a line). A△B=(A−B)∪(B−A)A \triangle B = (A - B) \cup (B - A)A△B=(A−B)∪(B−A) . In F7F_7F7​ the symmetric difference of two distinct circuits is always a circuit.

34. [Binary matroids] In the non-Fano plane F7−F_7^-F7−​ ( efgefgefg is not a line), find a circuit CCC and a cocircuit C∗C^*C∗ with ∣C∩C∗∣|C \cap C^*|∣C∩C∗∣ odd.

    C={d,e,f,g}\boldsymbol{C = \{d, e, f, g\}}C={d,e,f,g} , C∗={a,d,e,f}\boldsymbol{C^* = \{a, d, e, f\}}C∗={a,d,e,f} , ∣C∩C∗∣=3|C \cap C^*| = 3∣C∩C∗∣=3 . defgdefgdefg has no three collinear points, so it is a circuit; adefadefadef is the complement of the line bcgbcgbcg , so it is a cocircuit.So F7−F_7^-F7−​ is not binary.

35. [Binary matroids] In the non-Fano plane F7−F_7^-F7−​ , which two circuits have a symmetric difference that is not a disjoint union of circuits?

    {d,e,f,g}△{a,d,e,f}={a,g}\boldsymbol{\{d, e, f, g\} \triangle \{a, d, e, f\} = \{a, g\}}{d,e,f,g}△{a,d,e,f}={a,g} , an independent set. {a,d,e,f}\{a, d, e, f\}{a,d,e,f} is both a circuit and a cocircuit of F7−F_7^-F7−​ .

36. [Binary matroids] What is the symmetric difference C1△C2△…△CkC_1 \triangle C_2 \triangle \dots \triangle C_kC1​△C2​△…△Ck​ of kkk sets?

    The set of elements that lie in an odd number of the CiC_iCi​ . Example: {1,2}△{2,3}△{2,4}={1,2,3,4}\{1, 2\} \triangle \{2, 3\} \triangle \{2, 4\} = \{1, 2, 3, 4\}{1,2}△{2,3}△{2,4}={1,2,3,4} ( 222 lies in three of the sets).

37. [Binary matroids] Theorem 8.15. Which three conditions on a matroid MMM are equivalent?

    Binary MMM is representable over F2\mathbb{F}_2F2​ . Example: F7F_7F7​ is represented by the columns of abcdefg101010101101101111000\begin{array}{ccccccc} a & b & c & d & e & f & g \\ \hline 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 \end{array}a101​b011​c111​d001​e110​f010​g100​​ Even intersections ∣C∩C∗∣|C \cap C^*|∣C∩C∗∣ is even for every circuit CCC and cocircuit C∗C^*C∗ . Example: in F7F_7F7​ , ∣{a,b,e}∩{b,d,e,g}∣=2|\{a, b, e\} \cap \{b, d, e, g\}|…

38. [Binary matroids] M=M(A)M = M(A)M=M(A) is represented over F2\mathbb{F}_2F2​ by a matrix AAA ; CCC is a circuit and C∗C^*C∗ a cocircuit.Why is ∣C∩C∗∣|C \cap C^*|∣C∩C∗∣ even?

    ∣C∩C∗∣≡(uA)⋅v=u(Av)=u⋅0=0(mod2)\boldsymbol{|C \cap C^*| \equiv (uA) \cdot v = u(Av) = u \cdot 0 = 0 \pmod 2}∣C∩C∗∣≡(uA)⋅v=u(Av)=u⋅0=0(mod2) vvv = incidence vector of CCC , so Av=0Av = 0Av=0 . The hyperplane E−C∗E - C^*E−C∗ consists of the columns xxx with u⋅x=0u \cdot x = 0u⋅x=0 for some row vector uuu , so uAuAuA (entries 0 or 1) is the incidence vector of C∗C^*C∗ . Matrix multiplication is associative.Example: A=e1e2e3e4e5e6e7e8e9e10e111111011000011000101000001011001000100110001010111100001A…

39. [Binary matroids] XXX meets each of the sets C1,…,CkC_1, \dots, C_kC1​,…,Ck​ in an even number of elements. Why does XXX meet C1△…△CkC_1 \triangle \dots \triangle C_kC1​△…△Ck​ in an even number of elements?

    ∣X∩(C1△…△Ck)∣≡∑i∣X∩Ci∣(mod2)\boldsymbol{|X \cap (C_1 \triangle \dots \triangle C_k)| \equiv \sum_i |X \cap C_i| \pmod 2}∣X∩(C1​△…△Ck​)∣≡∑i​∣X∩Ci​∣(mod2) The incidence vector of the symmetric difference is the sum mod 2 of the incidence vectors of the CiC_iCi​ , and the dot product with the incidence vector of XXX is linear.Example: X={1,2}X = \{1, 2\}X={1,2} , C1={1,2,3}C_1 = \{1, 2, 3\}C1​={1,2,3} , C2={1,2,4}C_2 = \{1, 2, 4\}C2​={1,2,4} : C1△C2={3,4}C_1 \triangle C_2 = \{3, 4\}C1​△C2​={3,4} m…

40. [Binary matroids] Assume ∣C∩C∗∣|C \cap C^*|∣C∩C∗∣ is even for every circuit CCC and cocircuit C∗C^*C∗ of MMM . D=C1△…△CkD = C_1 \triangle \dots \triangle C_kD=C1​△…△Ck​ is a nonempty symmetric difference of circuits.Why is DDD dependent?

    Otherwise some cocircuit C∗C^*C∗ meets DDD in exactly one element, yet meets every CiC_iCi​ , and so DDD , evenly. If DDD were independent: extend DDD to a basis BBB , pick e∈De \in De∈D ; C∗=E−B−e‾C^* = E - \overline{B - e}C∗=E−B−e​ (complement of the hyperplane spanned by B−eB - eB−e ) meets BBB , and so DDD , only in eee .Then: DDD contains a circuit C′C'C′ , and D−C′=D△C′D - C' = D \triangle C'D−C′=D△C′ is again a symmetric difference of circuits; repeating splits DDD into di…

41. [Binary matroids] Assume the symmetric difference of any circuits of MMM (ground set EEE , ∣E∣=n|E| = n∣E∣=n ) is a disjoint union of circuits.How does the proof build a representation of MMM over F2\mathbb{F}_2F2​ ?

    Let W⊆F2nW \subseteq \mathbb{F}_2^nW⊆F2n​ be spanned by the incidence vectors of the circuits; a matrix whose rows are a basis of W⊥W^\perpW⊥ represents MMM . By the assumption, every vector of WWW is the incidence vector of a disjoint union of circuits.Example: Fano plane F7F_7F7​ . WWW has dimension 4, with basis the circuits abe,acf,adg,bdfabe, acf, adg, bdfabe,acf,adg,bdf (that 4×74 \times 74×7 matrix represents F7∗F_7^*F7∗​ ). W⊥W^\perpW⊥ has dimension 3 and basis the rows of abcdefg101010…

42. [Binary matroids] Corollary 8.19. When is a family C\mathcal{C}C of subsets of a finite set EEE the set of circuits of a binary matroid?

    No empty circuit ∅∉C\emptyset \notin \mathcal{C}∅∈/C . No containment If C1,C2∈CC_1, C_2 \in \mathcal{C}C1​,C2​∈C and C1⊆C2C_1 \subseteq C_2C1​⊆C2​ , then C1=C2C_1 = C_2C1​=C2​ . Example: in F7F_7F7​ , {a,b,e}\{a, b, e\}{a,b,e} and {a,b,e,c}\{a, b, e, c\}{a,b,e,c} are not both circuits. Symmetric differences If C1,C2∈CC_1, C_2 \in \mathcal{C}C1​,C2​∈C and C1≠C2C_1 \neq C_2C1​=C2​ , then C1△C2C_1 \triangle C_2C1​△C2​ is a disjoint union of members of C\mathcal{C}C . Example: in F7F_7F7​ , {e,f,…

43. [Binary matroids] Corollary 8.20. How are binary matroids characterized by cocircuits?

    MMM is binary if and only if C1∗△C2∗C_1^* \triangle C_2^*C1∗​△C2∗​ is a disjoint union of cocircuits for any two cocircuits C1∗,C2∗C_1^*, C_2^*C1∗​,C2∗​ . The dual of a binary matroid is binary, and the cocircuits of MMM are the circuits of M∗M^*M∗ .Example: in F7F_7F7​ , {c,d,f,g}△{b,d,e,g}={b,c,e,f}\{c, d, f, g\} \triangle \{b, d, e, g\} = \{b, c, e, f\}{c,d,f,g}△{b,d,e,g}={b,c,e,f} , the complement of the line adgadgadg , a cocircuit.

44. [Summary of excluded minor results] When is a graph HHH a topological minor of a graph GGG ?

    HHH is obtained from GGG by deleting edges and contracting edges incident with vertices of degree 2. Contracting an edge at a degree-2 vertex erases that vertex from the middle of a path.

45. [Summary of excluded minor results] Theorem 8.22 (Kuratowski; the book names Wagner). A graph GGG is planar if and only if … ?

    GGG has neither K3,3K_{3,3}K3,3​ nor K5K_5K5​ as a topological minor.

46. [Summary of excluded minor results] How does Kuratowski's theorem show that the Petersen graph is not planar?

    Delete the edges dedede and fgfgfg , then contract bd,ce,fy,gzbd, ce, fy, gzbd,ce,fy,gz : the result is K3,3K_{3,3}K3,3​ . After the deletions, d,e,f,gd, e, f, gd,e,f,g have degree 2. Each of a,b,ca, b, ca,b,c is adjacent to each of x,y,zx, y, zx,y,z .

47. [Summary of excluded minor results] Theorem 8.24. In terms of matroid minors, when is a graph GGG planar?

    When the cycle matroid M(G)M(G)M(G) has no minor isomorphic to M(K5)M(K_5)M(K5​) or M(K3,3)M(K_{3,3})M(K3,3​) . If HHH is a topological minor of GGG , then M(H)M(H)M(H) is a matroid minor of M(G)M(G)M(G) .

48. [Summary of excluded minor results] Why are M(K5)∗M(K_5)^*M(K5​)∗ and M(K3,3)∗M(K_{3,3})^*M(K3,3​)∗ excluded minors for the class of graphic matroids?

    GGG is planar if and only if M(G)∗M(G)^*M(G)∗ is graphic, and K5K_5K5​ , K3,3K_{3,3}K3,3​ are not planar, so M(K5)∗M(K_5)^*M(K5​)∗ , M(K3,3)∗M(K_{3,3})^*M(K3,3​)∗ are not graphic. Their proper minors are duals of proper minors of M(K5)M(K_5)M(K5​) , M(K3,3)M(K_{3,3})M(K3,3​) , which are cycle matroids of planar graphs, so these duals are graphic.

49. [Summary of excluded minor results] Which matroids are the excluded minors for cographic matroids (duals of graphic matroids)?

    U2,4, F7, F7∗, M(K5), M(K3,3)\boldsymbol{U_{2,4}, \ F_7, \ F_7^*, \ M(K_5), \ M(K_{3,3})}U2,4​, F7​, F7∗​, M(K5​), M(K3,3​) The duals of the excluded minors for graphic matroids ( U2,4U_{2,4}U2,4​ is self-dual, F7↔F7∗F_7 \leftrightarrow F_7^*F7​↔F7∗​ ). By Tutte.

50. [Summary of excluded minor results] Which matroids are the excluded minors for planar graphic matroids (graphic and cographic)?

    U2,4, F7, F7∗, M(K5), M(K3,3), M(K5)∗, M(K3,3)∗\boldsymbol{U_{2,4}, \ F_7, \ F_7^*, \ M(K_5), \ M(K_{3,3}), \ M(K_5)^*, \ M(K_{3,3})^*}U2,4​, F7​, F7∗​, M(K5​), M(K3,3​), M(K5​)∗, M(K3,3​)∗ The union of the lists for graphic and for cographic matroids. By Tutte.

51. [Summary of excluded minor results] What is the genus of a graph GGG ?

    The minimum number of handles to add to a sphere so that GGG can be drawn on the surface without edge crossings. One handle per crossing of a drawing on the sphere suffices, so every graph has a genus.Example: K5K_5K5​ and K3,3K_{3,3}K3,3​ have genus 1: they are not planar but can be drawn on a torus without crossings.

52. [Summary of excluded minor results] Graph Minor Theorem (Robertson and Seymour). What does it say about an infinite family of graphs?

    It contains two graphs GGG and HHH with GGG a minor of HHH . Graphs are well-quasi-ordered by the minor relation: no infinite antichain. Consequence: every surface has only finitely many excluded minors. The proof spans more than 20 papers.

53. [Summary of excluded minor results] When is an integer matrix unimodular, and when is a matroid regular (unimodular)?

    Unimodular: every k×kk \times kk×k submatrix has determinant 000 , 111 or −1-1−1 . Regular: representable over Q\mathbb{Q}Q by a unimodular matrix. 1×11 \times 11×1 submatrices count, so all entries are 000 , 111 or −1-1−1 .Example: [1101]\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}[10​11​] is unimodular; [111−1]\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}[11​1−1​] is not (determinant −2-2−2 ).

54. [Summary of excluded minor results] Theorem 8.27. A matroid MMM is regular if and only if … ?

    MMM is representable over every field. Example: U2,3U_{2,3}U2,3​ is regular: the columns (1,0),(0,1),(1,1)(1, 0), (0, 1), (1, 1)(1,0),(0,1),(1,1) form a unimodular matrix.

55. [Summary of excluded minor results] A matroid is regular if it is represented over Q\mathbb{Q}Q by a unimodular matrix (every square submatrix has determinant 000 or ±1\pm 1±1 ).Why does a unimodular representation AAA represent MMM over every field?

    Each r×rr \times rr×r submatrix has determinant 000 or ±1\pm 1±1 , and ±1\pm 1±1 is nonzero in every field, so the same column sets are bases over every field. The converse (representable over every field ⇒\Rightarrow⇒ regular) takes work: find one matrix representing MMM over both F2\mathbb{F}_2F2​ and F3\mathbb{F}_3F3​ , then show by induction that its square submatrices have determinants 0,±10, \pm 10,±1 .

56. [Summary of excluded minor results] Theorem 8.28. Graphic matroids are regular. Which unimodular matrix represents M(G)M(G)M(G) ?

    The vertex–edge incidence matrix with one of the two 1's in each column changed to −1-1−1 (an orientation of the edges). Example: abcde11−10102011003−10−10−14000−11\begin{array}{c|ccccc} & a & b & c & d & e \\ \hline 1 & 1 & -1 & 0 & 1 & 0 \\ 2 & 0 & 1 & 1 & 0 & 0 \\ 3 & -1 & 0 & -1 & 0 & -1 \\ 4 & 0 & 0 & 0 & -1 & 1 \end{array}1234​a10−10​b−1100​c01−10​d100−1​e00−11​​

57. [Summary of excluded minor results] Theorem 8.29 (Tutte). A matroid is binary if and only if … ?

    It has no U2,4U_{2,4}U2,4​ minor, i.e. U2,4U_{2,4}U2,4​ is the only excluded minor for binary matroids. The first excluded minor characterization, by Tutte.Example: the non-Fano plane F7−F_7^-F7−​ is not binary: F7−/e−{b,d}≅U2,4F_7^-/e - \{b, d\} \cong U_{2,4}F7−​/e−{b,d}≅U2,4​ .

58. [Summary of excluded minor results] Why is U2,4U_{2,4}U2,4​ an excluded minor for binary matroids?

    F22\mathbb{F}_2^2F22​ has only 3 nonzero vectors, so U2,4U_{2,4}U2,4​ (4 points, no two parallel, rank 2) is not binary; its proper minors are uniform with at most 3 elements, all binary.

59. [Summary of excluded minor results] Proof that a non-binary matroid MMM of rank rrr has a U2,4U_{2,4}U2,4​ minor. Binary means: ∣C∩C∗∣|C \cap C^*|∣C∩C∗∣ is even for every circuit CCC and cocircuit C∗C^*C∗ .Why are there a circuit CCC and a cocircuit C∗C^*C∗ with ∣C∩C∗∣≥3|C \cap C^*| \ge 3∣C∩C∗∣≥3 ?

    MMM is not binary, so some ∣C∩C∗∣|C \cap C^*|∣C∩C∗∣ is odd, and ∣C∩C∗∣=1|C \cap C^*| = 1∣C∩C∗∣=1 never happens in any matroid.

60. [Summary of excluded minor results] Proof that a non-binary matroid MMM of rank rrr has a U2,4U_{2,4}U2,4​ minor. CCC is a circuit and C∗C^*C∗ a cocircuit with x,y,z∈C∩C∗x, y, z \in C \cap C^*x,y,z∈C∩C∗ ; H=E−C∗H = E - C^*H=E−C∗ is a hyperplane.Which flat FFF does the proof use, and which four hyperplanes?

    A flat F⊆HF \subseteq HF⊆H of rank r−2r - 2r−2 with basis a1,…,ar−2a_1, \dots, a_{r-2}a1​,…,ar−2​ such that C={x,y,z,a1,…,ar−2}C = \{x, y, z, a_1, \dots, a_{r-2}\}C={x,y,z,a1​,…,ar−2​} ; the hyperplanes HHH , F∪x‾\overline{F \cup x}F∪x , F∪y‾\overline{F \cup y}F∪y​ , F∪z‾\overline{F \cup z}F∪z covering FFF . The sketch assumes, without justification, that FFF can be chosen with C∩FC \cap FC∩F a basis of FFF (so CCC is a spanning circuit).

61. [Summary of excluded minor results] Proof that a non-binary matroid MMM of rank rrr has a U2,4U_{2,4}U2,4​ minor. C={x,y,z,a1,…,ar−2}C = \{x, y, z, a_1, \dots, a_{r-2}\}C={x,y,z,a1​,…,ar−2​} is a circuit, {a1,…,ar−2}\{a_1, \dots, a_{r-2}\}{a1​,…,ar−2​} a basis of a flat FFF , and F⊆HF \subseteq HF⊆H , a hyperplane avoiding x,y,zx, y, zx,y,z .Why are HHH , F∪x‾\overline{F \cup x}F∪x , F∪y‾\overline{F \cup y}F∪y​ , F∪z‾\overline{F \cup z}F∪z four distinct hyperplanes?

    x,y,z∉Hx, y, z \notin Hx,y,z∈/H ; and F∪x‾=F∪y‾\overline{F \cup x} = \overline{F \cup y}F∪x=F∪y​ would make {x,y,a1,…,ar−2}\{x, y, a_1, \dots, a_{r-2}\}{x,y,a1​,…,ar−2​} dependent, but it is a proper subset of the circuit CCC . {x,y,a1,…,ar−2}\{x, y, a_1, \dots, a_{r-2}\}{x,y,a1​,…,ar−2​} has rrr elements and is independent, so it is a basis, so y∉F∪x‾y \notin \overline{F \cup x}y∈/F∪x .

62. [Summary of excluded minor results] MMM has a flat FFF of rank r(M)−2r(M) - 2r(M)−2 covered by four distinct hyperplanes.How do you get a U2,4U_{2,4}U2,4​ minor?

    Contract a basis of FFF (rank 2 remains), delete the rest of FFF (now loops), then keep one point from each of the four rank-1 flats. The four hyperplanes covering FFF become four distinct points of a rank-2 matroid.

63. [Summary of excluded minor results] Corollary 8.30. In terms of flats, when is a matroid MMM of rank rrr binary?

    When no flat of rank r−2r - 2r−2 is covered by four hyperplanes. One direction is the Scum Theorem: a U2,4U_{2,4}U2,4​ minor gives a flat whose upper interval is the lattice of U2,4U_{2,4}U2,4​ .Example: in F7−F_7^-F7−​ the point eee (rank 1=3−21 = 3 - 21=3−2 ) is covered by the four lines abe,cde,ef,egabe, cde, ef, egabe,cde,ef,eg ; in F7F_7F7​ every point is on exactly three lines.

64. [Summary of excluded minor results] Which matroids are the excluded minors for regular matroids?

    U2,4, F7, F7∗\boldsymbol{U_{2,4}, \ F_7, \ F_7^*}U2,4​, F7​, F7∗​ By Tutte. F7F_7F7​ is binary but not regular: it is representable only over fields of characteristic 2.

65. [Summary of excluded minor results] Which matroids are the excluded minors for ternary matroids (representable over F3\mathbb{F}_3F3​ )?

    U2,5, U3,5, F7, F7∗\boldsymbol{U_{2,5}, \ U_{3,5}, \ F_7, \ F_7^*}U2,5​, U3,5​, F7​, F7∗​ Reid (unpublished), Bixby, Seymour.

66. [Summary of excluded minor results] How many excluded minors do the quaternary matroids (representable over F4\mathbb{F}_4F4​ ) have?

    Exactly seven, the largest with 8 elements (published in 2000). All the known lists consist of small matroids: the largest excluded minors for graphic, cographic, planar graphic, regular, binary and ternary matroids are M(K5)M(K_5)M(K5​) and M(K5)∗M(K_5)^*M(K5​)∗ , with 10 elements.

67. [Summary of excluded minor results] What does Rota's conjecture say?

    For each finite field F\mathbb{F}F , the class of F\mathbb{F}F -representable matroids has finitely many excluded minors. When the book was written it was proved for F2,F3,F4\mathbb{F}_2, \mathbb{F}_3, \mathbb{F}_4F2​,F3​,F4​ and open from F5\mathbb{F}_5F5​ on. (Geelen, Gerards and Whittle announced a proof in 2014.)

68. [Summary of excluded minor results] Which uniform matroid is an easy excluded minor for Fq\mathbb{F}_qFq​ -representability, and why is it not representable?

    U2,q+2\boldsymbol{U_{2,q+2}}U2,q+2​ (and its dual Uq,q+2U_{q,q+2}Uq,q+2​ ): a rank-2 matroid over Fq\mathbb{F}_qFq​ without parallel points has at most q+1q + 1q+1 points. Fq2\mathbb{F}_q^2Fq2​ has q2−1q^2 - 1q2−1 nonzero vectors, in classes of q−1q - 1q−1 parallel vectors: q+1q + 1q+1 points. More generally (S. Ball), Ur,p+2U_{r,p+2}Ur,p+2​ is an excluded minor for Fp\mathbb{F}_pFp​ , ppp prime, for 2≤r≤p2 \le r \le p2≤r≤p .Example: q=2q = 2q=2 : U2,4U_{2,4}U2,4​ (binary); q=3q = 3q=3 : U2,5U_…

69. [Summary of excluded minor results] What does the well-quasi-ordered conjecture for matroids say, and what is known?

    Every infinite family M1,M2,…M_1, M_2, \dotsM1​,M2​,… of matroids representable over Fq\mathbb{F}_qFq​ has MiM_iMi​ a minor of MjM_jMj​ for some i≠ji \neq ji=j . Proved for binary matroids by Geelen, Gerards and Whittle. It is the matroid version of the Graph Minor Theorem.

70. [Summary of excluded minor results] Why is the well-quasi-ordered conjecture false for matroids over infinite fields?

    Brylawski: rank-3 matroids MnM_nMn​ on a1,…,an,b1,…,bna_1, \dots, a_n, b_1, \dots, b_na1​,…,an​,b1​,…,bn​ with three-point lines {ai,bi,ai+1}\{a_i, b_i, a_{i+1}\}{ai​,bi​,ai+1​} (indices mod nnn ) are all representable over Q\mathbb{Q}Q , and no MiM_iMi​ is a minor of another MjM_jMj​ . M6M_6M6​ .

71. [Summary of excluded minor results] How are the classes of binary, ternary, regular, graphic, cographic and planar graphic matroids related?

    Regular = binary ∩\cap∩ ternary; graphic and cographic ⊆\subseteq⊆ regular; planar graphic = graphic ∩\cap∩ cographic.