Ch.3: New matroids from old

Chapter 3 of the book "Matroids: A Geometric Introduction" by Gary Gordon and Jennifer McNulty (2012) 3.1. New matroids from old 3.2. Matroid deletion and contraction 3.3. Deletion and contraction in graphs 3.4. Duality in matroids 3.5. Graphic and representable duality 3.6. Direct sums and connectivity

137 flashcards · Mathematics · by lakesare

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

1. [New matroids from old] Which two questions does the study of new matroids from old ask?

   How to build a new matroid from a given matroid, and when a matroid decomposes as a union or sum of smaller matroids. The first two operations, deletion and contraction, come from graph theory.

2. [Matroid deletion and contraction] In terms of bases, when is an element eee of a matroid an isthmus, and when is eee a loop?

   Isthmus: eee is in every basis. Loop: eee is in no basis. Example: in the matroid on {a,b,c,d}\{a, b, c, d\}{a,b,c,d} with bases {a,b}\{a, b\}{a,b} and {a,c}\{a, c\}{a,c} , aaa is an isthmus and ddd is a loop.

3. [Matroid deletion and contraction] MMM is a matroid on EEE with independent sets I\mathcal{I}I , and e∈Ee \in Ee∈E is not an isthmus. What are the ground set and the independent sets of the deletion M−eM - eM−e ?

   Ground set E−{e}E - \{e\}E−{e} ; III is independent in M−eM - eM−e iff e∉Ie \notin Ie∈/I and III is independent in MMM . Example: if the independent sets of MMM are ∅,a,b,ab\emptyset, a, b, ab∅,a,b,ab , then those of M−aM - aM−a are ∅,b\emptyset, b∅,b .

4. [Matroid deletion and contraction] MMM is a matroid on EEE with independent sets I\mathcal{I}I , and e∈Ee \in Ee∈E is not a loop. What are the ground set and the independent sets of the contraction M/eM/eM/e ?

   Ground set E−{e}E - \{e\}E−{e} ; I−{e}I - \{e\}I−{e} is independent in M/eM/eM/e iff e∈Ie \in Ie∈I and III is independent in MMM . Equivalently: a set III with e∉Ie \notin Ie∈/I is independent in M/eM/eM/e iff I∪{e}I \cup \{e\}I∪{e} is independent in MMM .Example: if the independent sets of MMM are ∅,a,b,ab\emptyset, a, b, ab∅,a,b,ab , then those of M/aM/aM/a are ∅,b\emptyset, b∅,b (from aaa and ababab ).

5. [Matroid deletion and contraction] MMM is the matroid on E={a,b,c,d}E = \{a, b, c, d\}E={a,b,c,d} with independent sets ∅,a,b,c,d,ab,ad,bc,cd\emptyset, a, b, c, d, ab, ad, bc, cd∅,a,b,c,d,ab,ad,bc,cd (writing ababab for {a,b}\{a, b\}{a,b} ). What are the independent sets and the bases of M−aM - aM−a and of M/aM/aM/a ?

   M−aM - aM−a : ∅,b,c,d,bc,cd\emptyset, b, c, d, bc, cd∅,b,c,d,bc,cd (bases bc,cdbc, cdbc,cd ). M/aM/aM/a : ∅,b,d\emptyset, b, d∅,b,d (bases b,db, db,d ). M−aM - aM−a : the independent sets without aaa . M/aM/aM/a : the independent sets with aaa are a,ab,ada, ab, ada,ab,ad ; removing aaa gives ∅,b,d\emptyset, b, d∅,b,d . ccc is an isthmus of M−aM - aM−a and a loop of M/aM/aM/a (drawn as a cloud).

6. [Matroid deletion and contraction] i(M)i(M)i(M) is the number of independent sets of a matroid MMM , and eee is neither an isthmus nor a loop. i(M)= ?i(M) = \; ?i(M)=?

   i(M)=i(M/e)+i(M−e)\boldsymbol{i(M) = i(M/e) + i(M - e)}i(M)=i(M/e)+i(M−e) The independent sets without eee are those of M−eM - eM−e ; the independent sets with eee , with eee removed, are those of M/eM/eM/e .Many quantities satisfy such a deletion-contraction recursion; they are studied as matroid invariants.Example: MMM on {a,b,c,d}\{a, b, c, d\}{a,b,c,d} with independent sets ∅,a,b,c,d,ab,ad,bc,cd\emptyset, a, b, c, d, ab, ad, bc, cd∅,a,b,c,d,ab,ad,bc,cd : 9=3+69 = 3 + 69=3+6 for e=ae = ae=a .

7. [Matroid deletion and contraction] Proposition 3.2 If eee is neither an isthmus nor a loop of a matroid MMM , then … ?

   M−eM - eM−e and M/eM/eM/e are both matroids (on E−{e}E - \{e\}E−{e} ). Proof: check that both families of sets satisfy the independent set axioms (I1) ∅\emptyset∅ is independent, (I2) subsets of independent sets are independent, (I3) augmentation.

8. [Matroid deletion and contraction] eee is neither an isthmus nor a loop of a matroid MMM . What are the bases of M−eM - eM−e and of M/eM/eM/e ?

   Deletion M−eM - eM−e The bases of MMM that do not contain eee . Example: MMM with bases ab,ad,bc,cdab, ad, bc, cdab,ad,bc,cd : M−aM - aM−a has bases bc,cdbc, cdbc,cd . Contraction M/eM/eM/e The bases of MMM that contain eee , with eee removed from each. Example: MMM with bases ab,ad,bc,cdab, ad, bc, cdab,ad,bc,cd : M/aM/aM/a has bases b,db, db,d .

9. [Matroid deletion and contraction] Why is the contraction M/eM/eM/e not defined when eee is a loop?

   No independent set contains eee , so M/eM/eM/e would have no independent sets at all, not even ∅\emptyset∅ . That violates axiom (I1): ∅\emptyset∅ is independent.Example: in the matroid on {e}\{e\}{e} where eee is a loop, the only independent set is ∅\emptyset∅ , which does not contain eee .

10. [Matroid deletion and contraction] Why is the deletion M−eM - eM−e not defined when eee is an isthmus?

    Every basis contains eee , so M−eM - eM−e would have no bases, but every matroid has a basis. The bases of M−eM - eM−e are the bases of MMM that avoid eee . Some authors instead define M−eM - eM−e as M/eM/eM/e for an isthmus (and M/eM/eM/e as M−eM - eM−e for a loop); this book never does.Example: in the matroid with bases ab,acab, acab,ac , no basis avoids the isthmus aaa .

11. [Matroid deletion and contraction] Proposition 3.7. For a matroid MMM : if eee is not an isthmus, r(M−e)= ?r(M - e) = \; ?r(M−e)=? if eee is not a loop, r(M/e)= ?r(M/e) = \; ?r(M/e)=?

    r(M−e)=r(M)\boldsymbol{r(M - e) = r(M)}r(M−e)=r(M) and r(M/e)=r(M)−1\boldsymbol{r(M/e) = r(M) - 1}r(M/e)=r(M)−1 Contraction reduces rank by 1; deletion of a non-isthmus keeps it.Example: MMM with bases ab,ad,bc,cdab, ad, bc, cdab,ad,bc,cd has rank 2; M−aM - aM−a (bases bc,cdbc, cdbc,cd ) has rank 2 and M/aM/aM/a (bases b,db, db,d ) has rank 1.

12. [Matroid deletion and contraction] Why is r(M/e)=r(M)−1r(M/e) = r(M) - 1r(M/e)=r(M)−1 when eee is not a loop, and why is r(M−e)=r(M)r(M - e) = r(M)r(M−e)=r(M) when eee is not an isthmus?

    A basis of M/eM/eM/e is a basis of MMM containing eee , minus eee ; and if r(M−e)<r(M)r(M - e) < r(M)r(M−e)<r(M) , every basis of MMM would contain eee . The second case means eee is an isthmus, which is excluded.

13. [Matroid deletion and contraction] How do you get a picture of the deletion M−eM - eM−e from a picture of a matroid MMM ?

    Erase the point eee , and erase every three-point line through eee . A set is independent in the new picture exactly when it is independent in MMM and avoids eee . Example: the Fano plane F7F_7F7​ and F7−gF_7 - gF7​−g ; the lines bcgbcgbcg , adgadgadg , efgefgefg disappear.

14. [Matroid deletion and contraction] The Fano plane F7F_7F7​ has rank 3 and the seven 3-point lines abe,acf,bcg,adg,bdf,cde,efgabe, acf, bcg, adg, bdf, cde, efgabe,acf,bcg,adg,bdf,cde,efg .Which are the 3-point lines of F7−gF_7 - gF7​−g ?

    abeabeabe , acfacfacf , bdfbdfbdf , cdecdecde : the four lines of F7F_7F7​ that avoid ggg .

15. [Matroid deletion and contraction] Why is F7−gF_7 - gF7​−g isomorphic to F7−bF_7 - bF7​−b (Fano plane F7F_7F7​ )?

    The automorphism group of F7F_7F7​ is transitive: some automorphism of F7F_7F7​ maps ggg to bbb . So every element of F7F_7F7​ "looks the same". For the same reason F7/aF_7/aF7​/a is isomorphic to F7/eF_7/eF7​/e .

16. [Matroid deletion and contraction] The set of all lines through a point is called a pencil of lines.

17. [Matroid deletion and contraction] How do you get a picture of the contraction M/eM/eM/e from a picture of a matroid MMM ?

    Project the other points from eee onto a "screen" of dimension one less. Place your eye at eee ; place the screen so that every line through eee meets the screen; project each other point along its line through eee . Example: F7/aF_7/aF7​/a . The lines abe,acf,adgabe, acf, adgabe,acf,adg through aaa become the double points be,cf,dgbe, cf, dgbe,cf,dg on a line.

18. [Matroid deletion and contraction] The Fano plane F7F_7F7​ has rank 3 and the seven 3-point lines abe,acf,bcg,adg,bdf,cde,efgabe, acf, bcg, adg, bdf, cde, efgabe,acf,bcg,adg,bdf,cde,efg .What does the contraction F7/eF_7/eF7​/e look like?

    Rank 2: the three double points ababab , cdcdcd , fgfgfg on one line. The three lines through eee are abeabeabe , cdecdecde , efgefgefg ; each one becomes a double point (a pair of parallel elements). The screen is drawn curved to collect the projected points.

19. [Matroid deletion and contraction] Proposition 3.8. For elements a,ba, ba,b of a matroid MMM (whenever all terms are defined), which three identities hold?

    (M−a)−b=(M−b)−a\boldsymbol{(M - a) - b = (M - b) - a}(M−a)−b=(M−b)−a , (M/a)/b=(M/b)/a\ \boldsymbol{(M/a)/b = (M/b)/a} (M/a)/b=(M/b)/a , (M/a)−b=(M−b)/a\ \boldsymbol{(M/a) - b = (M - b)/a} (M/a)−b=(M−b)/a Deletions and contractions commute with themselves and with each other.Example: for the uniform matroid U3,4U_{3,4}U3,4​ on {a,b,c,d}\{a, b, c, d\}{a,b,c,d} , both (M/a)/b(M/a)/b(M/a)/b and (M/b)/a(M/b)/a(M/b)/a are U1,2U_{1,2}U1,2​ on {c,d}\{c, d\}{c,d} .

20. [Matroid deletion and contraction] MMM is the matroid on E={a,b,c,d}E = \{a, b, c, d\}E={a,b,c,d} with independent sets ∅,a,b,c,d,ab,ad,bc,cd\emptyset, a, b, c, d, ab, ad, bc, cd∅,a,b,c,d,ab,ad,bc,cd (writing ababab for {a,b}\{a, b\}{a,b} ).Compute (M/a)−b(M/a) - b(M/a)−b and (M−b)/a(M - b)/a(M−b)/a .

    Both: ground set {c,d}\{c, d\}{c,d} with independent sets ∅,d\emptyset, d∅,d . M/aM/aM/a has independent sets ∅,b,d\emptyset, b, d∅,b,d ; deleting bbb leaves ∅,d\emptyset, d∅,d . M−bM - bM−b has independent sets ∅,a,c,d,ad,cd\emptyset, a, c, d, ad, cd∅,a,c,d,ad,cd ; contracting aaa (from a,ada, ada,ad ) gives ∅,d\emptyset, d∅,d .

21. [Matroid deletion and contraction] a,ba, ba,b are elements of a matroid MMM . What must hold for each side of these identities to be defined? (M−a)−b=(M−b)−a(M - a) - b = (M - b) - a(M−a)−b=(M−b)−a , (M/a)/b=(M/b)/a\ (M/a)/b = (M/b)/a (M/a)/b=(M/b)/a , (M/a)−b=(M−b)/a\ (M/a) - b = (M - b)/a (M/a)−b=(M−b)/a

    Two deletions bbb is not an isthmus of M−aM - aM−a , and aaa is not an isthmus of M−bM - bM−b . Example: in U1,2U_{1,2}U1,2​ on {a,b}\{a, b\}{a,b} , bbb is an isthmus of M−aM - aM−a , so (M−a)−b(M - a) - b(M−a)−b is undefined. Two contractions {a,b}\{a, b\}{a,b} is independent in MMM . Example: if {a,b}\{a, b\}{a,b} is a circuit, bbb is a loop of M/aM/aM/a , so (M/a)/b(M/a)/b(M/a)/b is undefined. A contraction and a deletion aaa is not a loop and bbb is not an isthmus. Example: if aaa is a loop…

22. [Matroid deletion and contraction] Why is (M/a)/b=(M/b)/a(M/a)/b = (M/b)/a(M/a)/b=(M/b)/a when {a,b}\{a, b\}{a,b} is independent in a matroid MMM ?

    Both have as independent sets: the independent sets of MMM containing both aaa and bbb , with aaa and bbb removed. That description does not depend on which element is contracted first.Example: in U3,4U_{3,4}U3,4​ on {a,b,c,d}\{a, b, c, d\}{a,b,c,d} the independent sets containing ababab are ab,abc,abdab, abc, abdab,abc,abd , so both sides have independent sets ∅,c,d\emptyset, c, d∅,c,d .

23. [Matroid deletion and contraction] Why may one write M/abM/abM/ab , M/a−bM/a - bM/a−b and M−abM - abM−ab without parentheses?

    Repeated deletions and contractions give the same matroid in any order. M/abM/abM/ab means M/{a,b}M/\{a, b\}M/{a,b} : take the independent sets containing {a,b}\{a, b\}{a,b} and remove aaa and bbb from each, all at once.Example: M/ab=(M/a)/b=(M/b)/aM/ab = (M/a)/b = (M/b)/aM/ab=(M/a)/b=(M/b)/a .

24. [Matroid deletion and contraction] eee is neither an isthmus nor a loop of a matroid MMM . When is CCC a circuit of M−eM - eM−e ?

    Iff e∉Ce \notin Ce∈/C and CCC is a circuit of MMM . Example: MMM on {a,b,c,d}\{a, b, c, d\}{a,b,c,d} with circuits acacac and bdbdbd : M−aM - aM−a has the single circuit bdbdbd .

25. [Matroid deletion and contraction] eee is neither an isthmus nor a loop of a matroid MMM . When is C⊆E−{e}C \subseteq E - \{e\}C⊆E−{e} a circuit of M/eM/eM/e ?

    Iff C∪{e}C \cup \{e\}C∪{e} is a circuit of MMM , or CCC is a circuit of MMM and CCC is the only circuit inside C∪{e}C \cup \{e\}C∪{e} . Example: MMM on {a,b,c,d}\{a, b, c, d\}{a,b,c,d} with circuits acacac and bdbdbd . M/aM/aM/a has the circuits ccc (since acacac is a circuit) and bdbdbd (the only circuit inside abdabdabd ).

26. [Matroid deletion and contraction] eee is neither an isthmus nor a loop of a matroid MMM , and A⊆EA \subseteq EA⊆E with e∉Ae \notin Ae∈/A . rM−e(A)= ?r_{M - e}(A) = \; ?rM−e​(A)=? rM/e(A)= ?\quad r_{M/e}(A) = \; ?rM/e​(A)=?

    rM−e(A)=rM(A)\boldsymbol{r_{M - e}(A) = r_M(A)}rM−e​(A)=rM​(A) and rM/e(A)=rM(A∪e)−1\boldsymbol{r_{M/e}(A) = r_M(A \cup e) - 1}rM/e​(A)=rM​(A∪e)−1 With A=E−{e}A = E - \{e\}A=E−{e} these give r(M−e)=r(M)r(M - e) = r(M)r(M−e)=r(M) and r(M/e)=r(M)−1r(M/e) = r(M) - 1r(M/e)=r(M)−1 .Example: in the Fano plane F7F_7F7​ with line abeabeabe : rF7/a({b,e})=r({a,b,e})−1=2−1=1r_{F_7/a}(\{b, e\}) = r(\{a, b, e\}) - 1 = 2 - 1 = 1rF7​/a​({b,e})=r({a,b,e})−1=2−1=1 , so b,eb, eb,e are parallel in F7/aF_7/aF7​/a…

27. [Matroid deletion and contraction] MMM has rank 4: a,b,ca, b, ca,b,c are on a line, and the planes with more than 3 points are abcefabcefabcef , abcdgabcdgabcdg , defgdefgdefg .What does the contraction M/aM/aM/a look like?

    Rank 3: b,cb, cb,c become a double point; bc,e,fbc, e, fbc,e,f and bc,d,gbc, d, gbc,d,g lie on two lines. The line abcabcabc through aaa becomes the double point bcbcbc ; the planes abcefabcefabcef and abcdgabcdgabcdg through aaa become lines. Up to symmetry the only other case is contracting a point on no 3-point line, such as fff .

28. [Matroid deletion and contraction] MMM has rank 4: a,b,ca, b, ca,b,c are on a line, and the planes with more than 3 points are abcefabcefabcef , abcdgabcdgabcdg , defgdefgdefg .What does the contraction M/fM/fM/f look like?

    Rank 3: the lines abceabceabce and degdegdeg , meeting at eee ; no double points. fff is on no 3-point line, so no two points become parallel. The planes abcefabcefabcef and defgdefgdefg through fff become the lines abceabceabce and degdegdeg .

29. [Deletion and contraction in graphs] GGG is a graph with cycle matroid M(G)M(G)M(G) (edges; a set of edges is independent iff it contains no cycle), and eee is an edge. Which graphs have cycle matroids M(G)−eM(G) - eM(G)−e and M(G)/eM(G)/eM(G)/e ?

    Deletion G−eG - eG−e Erase the edge eee . Then M(G−e)=M(G)−eM(G - e) = M(G) - eM(G−e)=M(G)−e . Example: in the square with diagonal aaa below, G−eG - eG−e leaves ddd hanging from one vertex. Contraction G/eG/eG/e Erase the edge eee and identify its two endpoints. Then M(G/e)=M(G)/eM(G/e) = M(G)/eM(G/e)=M(G)/e . Example: in G/eG/eG/e below, ddd becomes parallel to aaa . Contraction shrinks the edge eee to a point.

30. [Deletion and contraction in graphs] The graph GGG has the cycles abcabcabc , adeadeade , bcdebcdebcde . What are the circuits of M(G−e)M(G - e)M(G−e) and of M(G/e)M(G/e)M(G/e) ?

    G−eG - eG−e : only abcabcabc . G/e\ G/e G/e : abcabcabc , adadad , bcdbcdbcd . In G−eG - eG−e the edge ddd is an isthmus. In G/eG/eG/e each cycle through eee loses eee : ade→adade \to adade→ad , bcde→bcdbcde \to bcdbcde→bcd .

31. [Deletion and contraction in graphs] GGG is a connected graph with vvv vertices and eee is an edge that is not a loop. What are r(M(G))r(M(G))r(M(G)) and r(M(G/e))r(M(G/e))r(M(G/e)) ?

    r(M(G))=v−1\boldsymbol{r(M(G)) = v - 1}r(M(G))=v−1 and r(M(G/e))=v−2\boldsymbol{r(M(G/e)) = v - 2}r(M(G/e))=v−2 A spanning tree has v−1v - 1v−1 edges, and G/eG/eG/e is connected with v−1v - 1v−1 vertices. This agrees with r(M/e)=r(M)−1r(M/e) = r(M) - 1r(M/e)=r(M)−1 .Example: the square with a diagonal has 4 vertices and rank 3; contracting a side gives a graph on 3 vertices, of rank 2.

32. [Deletion and contraction in graphs] A matroid M[A]M[A]M[A] whose ground set is the set of columns of a matrix AAA , with linearly independent sets of columns as independent sets, is called representable.

    Example: A=[101011]A = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}A=[10​01​11​] gives U2,3U_{2,3}U2,3​ : any two columns are independent, all three are not.

33. [Deletion and contraction in graphs] eee is not an isthmus of the matroid M[A]M[A]M[A] of a matrix AAA . Which matrix represents M[A]−eM[A] - eM[A]−e ?

    A−eA - eA−e : the matrix AAA with the column of eee erased. Example: erasing the column eee from [101011]\begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}[10​01​11​] (columns a,b,ea, b, ea,b,e ) gives [1001]\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}[10​01​] , which represents U2,2U_{2,2}U2,2​ .

34. [Deletion and contraction in graphs] eee is not a loop of the matroid M[A]M[A]M[A] of a matrix AAA . How do you get a matrix A/eA/eA/e that represents M[A]/eM[A]/eM[A]/e ?

    Row-reduce AAA until column eee has exactly one nonzero entry, in row rrr ; then delete both column eee and row rrr . It works because elementary row operations do not change the linear dependences among the columns.Example: for [101011]\begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}[10​01​11​] (columns a,b,ea, b, ea,b,e ), subtract row 1 from row 2: [101−110]\begin{bmatrix} 1 & 0 & 1 \\ -1 & 1 & 0 \end{bmatrix}[1−1​01​10​] . Deleting row 1 and column eee gives [−11]\begin{bmatrix} -1 & 1…

35. [Deletion and contraction in graphs] The columns of this matrix are a,b,c,d,ea, b, c, d, ea,b,c,d,e : A=[100110102−100101]A = \begin{bmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 2 & -1 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix}A=⎣⎡​100​010​001​120​1−11​⎦⎤​ Describe the matroid M[A]M[A]M[A] .

    Rank 3: a,b,da, b, da,b,d lie on a line; ccc and eee lie on no 3-point line. a,b,da, b, da,b,d have third coordinate 0, so they span only a plane; every other triple has a nonzero determinant.

36. [Deletion and contraction in graphs] The columns of this matrix are a,b,c,d,ea, b, c, d, ea,b,c,d,e : A=[100110102−100101]A = \begin{bmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 2 & -1 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix}A=⎣⎡​100​010​001​120​1−11​⎦⎤​ Compute a matrix A/eA/eA/e representing M[A]/eM[A]/eM[A]/e .

    A/e=[1103−101−1]\boldsymbol{A/e = \begin{bmatrix} 1 & 1 & 0 & 3 \\ -1 & 0 & 1 & -1 \end{bmatrix}}A/e=[1−1​10​01​3−1​] (columns a,b,c,da, b, c, da,b,c,d ) Adding row 1 to row 2 and subtracting row 1 from row 3 leaves column eee with its only nonzero entry in row 1: B=[1001111030−101−10]B = \begin{bmatrix} 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 3 & 0 \\ -1 & 0 & 1 & -1 & 0 \end{bmatrix}B=⎣⎡​11−1​010​001​13−1​100​⎦⎤​ . Then delete row 1 and column eee . M[A/e]M[A/e]M[A/e] is four points on a line ( U2,4…

37. [Deletion and contraction in graphs] When is the element eee a loop of the matroid M[A]M[A]M[A] of a matrix AAA ?

    Iff the column of eee is the zero vector. Example: in [1000]\begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}[10​00​] the second column is a loop.

38. [Deletion and contraction in graphs] How do you recognize from a matrix AAA that the element eee is an isthmus of M[A]M[A]M[A] ?

    Row-reduce until column eee has a single nonzero entry, in row rrr ; eee is an isthmus iff that entry is also the only nonzero entry of row rrr . The procedure fails for a zero column (a loop), another reason not to contract loops.Example: in [100101020010]\begin{bmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 0 \end{bmatrix}⎣⎡​100​010​001​120​⎦⎤​ (columns a,b,c,da, b, c, da,b,c,d ), column ccc and row 3 have their only nonzero entry in the same place, so ccc is an isthmus.

39. [Duality in matroids] MMM is a matroid on EEE . What is the dual matroid M∗M^*M∗ ?

    The matroid on EEE whose bases are the complements E−BE - BE−B of the bases BBB of MMM . B(M∗)={E−B:B∈B(M)}\mathcal{B}(M^*) = \{E - B : B \in \mathcal{B}(M)\}B(M∗)={E−B:B∈B(M)} Example: U1,3U_{1,3}U1,3​ on {a,b,c}\{a, b, c\}{a,b,c} has bases a,b,ca, b, ca,b,c , so its dual has bases bc,ac,abbc, ac, abbc,ac,ab : it is U2,3U_{2,3}U2,3​ .

40. [Duality in matroids] When is a graph planar?

    When it can be drawn in the plane with no two edges crossing. Planarity is a property of the graph, not of one drawing; a drawing without crossings is an embedding. Example: K4K_4K4​ is planar, although the left drawing has a crossing.

41. [Duality in matroids] GGG is a planar graph drawn in the plane with no crossings. How is the dual graph G∗G^*G∗ formed?

    One vertex inside each region of GGG ; an edge e∗e^*e∗ joins two such vertices when their regions share the edge eee . GGG and G∗G^*G∗ can be drawn together so that each edge eee crosses exactly one edge of G∗G^*G∗ , namely e∗e^*e∗ . Example: GGG (bold) with G∗G^*G∗ drawn over it.

42. [Duality in matroids] GGG is a plane graph with dual G∗G^*G∗ , and TTT is a spanning tree of GGG . What do the edges e∗e^*e∗ with e∉Te \notin Te∈/T form?

    A spanning tree of G∗G^*G∗ . This fact about complements of spanning trees motivates the definition of the dual matroid. Example: {a,c,d}\{a, c, d\}{a,c,d} is a spanning tree of GGG , and {b∗,e∗}\{b^*, e^*\}{b∗,e∗} is a spanning tree of G∗G^*G∗ .

43. [Duality in matroids] MMM is the rank-3 matroid on E={a,b,c,d,e}E = \{a, b, c, d, e\}E={a,b,c,d,e} with circuits abcabcabc , cdecdecde and abdeabdeabde (writing abcabcabc for {a,b,c}\{a, b, c\}{a,b,c} ).What are the bases of M∗M^*M∗ , and what does M∗M^*M∗ look like?

    M∗M^*M∗ has rank 2, with bases all pairs except ababab and dedede : a,ba, ba,b are parallel, d,ed, ed,e are parallel. The bases of MMM are all 3-sets except abcabcabc and cdecdecde ; their complements are all 2-sets except dedede and ababab . Example: the basis abdabdabd of MMM gives the basis cecece of M∗M^*M∗ .

44. [Duality in matroids] Which three conditions on a family B\mathcal{B}B of subsets of EEE make B\mathcal{B}B the family of bases of a matroid (the version used to prove that the dual is a matroid)?

    (B1) B≠∅\mathcal{B} \neq \emptysetB=∅ . (B2′) If B1,B2∈BB_1, B_2 \in \mathcal{B}B1​,B2​∈B , then ∣B1∣=∣B2∣|B_1| = |B_2|∣B1​∣=∣B2​∣ . (B3′) Strong basis exchange If B1,B2∈BB_1, B_2 \in \mathcal{B}B1​,B2​∈B and x∈B1−B2x \in B_1 - B_2x∈B1​−B2​ , then some y∈B2−B1y \in B_2 - B_1y∈B2​−B1​ has both B1−x∪y∈BB_1 - x \cup y \in \mathcal{B}B1​−x∪y∈B and B2−y∪x∈BB_2 - y \cup x \in \mathcal{B}B2​−y∪x∈B . Example: bases ab,bcab, bcab,bc of U2,3U_{2,3}U2,3​ , x=ax = ax=a : y=cy = cy=c gives bcbcbc and ababa…

45. [Duality in matroids] The basis axiom "for B1,B2∈BB_1, B_2 \in \mathcal{B}B1​,B2​∈B and x∈B1−B2x \in B_1 - B_2x∈B1​−B2​ , some y∈B2−B1y \in B_2 - B_1y∈B2​−B1​ makes both B1−x∪yB_1 - x \cup yB1​−x∪y and B2−y∪xB_2 - y \cup xB2​−y∪x bases" is called strong basis exchange.

46. [Duality in matroids] Theorem 3.15 Let MMM be a matroid on EEE with bases B\mathcal{B}B . Then {E−B:B∈B}\{E - B : B \in \mathcal{B}\}{E−B:B∈B} … ?

    is the family of bases of a matroid (so the dual M∗M^*M∗ is a matroid).

47. [Duality in matroids] Claim: for the bases B\mathcal{B}B of a matroid on EEE , the family B∗={E−B:B∈B}\mathcal{B}^* = \{E - B : B \in \mathcal{B}\}B∗={E−B:B∈B} satisfies (B1) nonempty, (B2′) equal sizes, (B3′) strong basis exchange.What is the key idea of the proof ( XcX^cXc denotes E−XE - XE−X )?

    (B1), (B2′) are immediate; for (B3′), take complements, apply strong exchange in MMM , and take complements again. All complements have size ∣E∣−r(M)|E| - r(M)∣E∣−r(M) . For x∈B1c−B2cx \in B_1^c - B_2^cx∈B1c​−B2c​ we have x∈B2−B1x \in B_2 - B_1x∈B2​−B1​ ; strong exchange in MMM gives y∈B1−B2y \in B_1 - B_2y∈B1​−B2​ with B1∪x−yB_1 \cup x - yB1​∪x−y and B2∪y−xB_2 \cup y - xB2​∪y−x bases. Their complements B1c∪y−xB_1^c \cup y - xB1c​∪y−x and B2c∪x−yB_2^c \cup x - yB2c​∪x−y are in B∗\mathcal{B}^*B∗…

48. [Duality in matroids] To show that the basis complements B∗={E−B}\mathcal{B}^* = \{E - B\}B∗={E−B} of a matroid satisfy basis exchange: for x∈B1c−B2cx \in B_1^c - B_2^cx∈B1c​−B2c​ we need yyy with B1c∪y−x∈B∗B_1^c \cup y - x \in \mathcal{B}^*B1c​∪y−x∈B∗ ( XcX^cXc denotes E−XE - XE−X ).Why does the proof need strong exchange (B3′) in MMM , and not ordinary exchange (B3)?

    Ordinary exchange in MMM for x∈B2−B1x \in B_2 - B_1x∈B2​−B1​ only gives B2∪y−xB_2 \cup y - xB2​∪y−x , whose complement B2c∪x−yB_2^c \cup x - yB2c​∪x−y is the wrong one. The exchange needed is on the side of B1cB_1^cB1c​ . It is easier to prove the stronger property for B∗\mathcal{B}^*B∗ from the stronger property for B\mathcal{B}B .

49. [Duality in matroids] Proposition 3.16. MMM is a matroid on EEE with dual M∗M^*M∗ . r(M)+r(M∗)= ?\ r(M) + r(M^*) = \; ? r(M)+r(M∗)=?

    ∣E∣\boldsymbol{|E|}∣E∣ A basis of M∗M^*M∗ is the complement of a basis of MMM .Example: the Fano plane F7F_7F7​ has rank 3, so its dual F7∗F_7^*F7∗​ has rank 7−3=47 - 3 = 47−3=4 .

50. [Duality in matroids] Proposition 3.17. For a matroid MMM , (M∗)∗= ?(M^*)^* = \; ?(M∗)∗=?

    M\boldsymbol{M}M The complement of the complement of a basis is the basis itself.

51. [Duality in matroids] MMM is the rank-3 matroid on E={a,b,c,d,e}E = \{a, b, c, d, e\}E={a,b,c,d,e} with circuits abcabcabc , cdecdecde and abdeabdeabde (writing abcabcabc for {a,b,c}\{a, b, c\}{a,b,c} ).How do the bases, independent sets, spanning sets, circuits and hyperplanes of M∗M^*M∗ correspond to sets of MMM ?

    Basis BBB is a basis of M∗M^*M∗ iff E−BE - BE−B is a basis of MMM . Example: cecece in M∗M^*M∗ , abdabdabd in MMM . Independent set III is independent in M∗M^*M∗ iff E−IE - IE−I is spanning in MMM . Example: ccc in M∗M^*M∗ , abdeabdeabde in MMM . Spanning set SSS is spanning in M∗M^*M∗ iff E−SE - SE−S is independent in MMM . Example: acacac in M∗M^*M∗ , bdebdebde in MMM . Circuit CCC is a circuit of M∗M^*M∗ iff E−CE - CE−C is a hyperplane of MMM . Example: ababab in M∗M^*M∗ (a parallel pair), t…

52. [Duality in matroids] What is a cocircuit of a matroid MMM on EEE ?

    The complement E−HE - HE−H of a hyperplane HHH of MMM . So the cocircuits of MMM are the circuits of M∗M^*M∗ .Example: in the Fano plane F7F_7F7​ the line efgefgefg is a hyperplane, so abcdabcdabcd is a cocircuit.

53. [Duality in matroids] Why is CCC a circuit of a matroid MMM on EEE iff E−CE - CE−C is a hyperplane of M∗M^*M∗ ?

    CCC is minimal with respect to not being contained in a basis of MMM iff E−CE - CE−C is maximal with respect to not containing a basis of M∗M^*M∗ . Complementation reverses inclusion and turns bases of MMM into bases of M∗M^*M∗ ; a hyperplane is a maximal set containing no basis (a maximal non-spanning set).

54. [Duality in matroids] The Fano plane F7F_7F7​ has rank 3 and the seven 3-point lines abe,acf,bcg,adg,bdf,cde,efgabe, acf, bcg, adg, bdf, cde, efgabe,acf,bcg,adg,bdf,cde,efg . A={a,b,c,d}A = \{a, b, c, d\}A={a,b,c,d} . Compute the rank r∗(A)r^*(A)r∗(A) of AAA in the dual F7∗F_7^*F7∗​ .

    r∗(A)=3\boldsymbol{r^*(A) = 3}r∗(A)=3 A basis of F7F_7F7​ meeting E−A=efgE - A = efgE−A=efg in as many elements as possible is B=aefB = aefB=aef ; its complement B′=bcdgB&#x27; = bcdgB′=bcdg is a basis of F7∗F_7^*F7∗​ with A∩B′=bcdA \cap B&#x27; = bcdA∩B′=bcd . In the picture of F7∗F_7^*F7∗​ (rank 4), the curved line through a,ba, ba,b meets the line through c,dc, dc,d , so a,b,c,da, b, c, da,b,c,d span only a plane.

55. [Duality in matroids] Theorem 3.20. MMM is a matroid on EEE with rank function rrr , and r∗r^*r∗ is the rank function of M∗M^*M∗ . For A⊆EA \subseteq EA⊆E : r∗(A)= ?\ r^*(A) = \; ? r∗(A)=?

    r∗(A)=r(E−A)+∣A∣−r(M)\boldsymbol{r^*(A) = r(E - A) + |A| - r(M)}r∗(A)=r(E−A)+∣A∣−r(M) With A=EA = EA=E : r(M∗)=0+∣E∣−r(M)r(M^*) = 0 + |E| - r(M)r(M∗)=0+∣E∣−r(M) .Example: in the Fano plane F7F_7F7​ with A=abcdA = abcdA=abcd : r∗(A)=r(efg)+4−3=2+4−3=3r^*(A) = r(efg) + 4 - 3 = 2 + 4 - 3 = 3r∗(A)=r(efg)+4−3=2+4−3=3 .

56. [Duality in matroids] What is the key idea of the proof that r∗(A)=r(E−A)+∣A∣−r(M)r^*(A) = r(E - A) + |A| - r(M)r∗(A)=r(E−A)+∣A∣−r(M) ( r∗r^*r∗ the rank function of the dual M∗M^*M∗ )?

    Choose a basis BBB of M∗M^*M∗ with ∣A∩B∣=r∗(A)|A \cap B| = r^*(A)∣A∩B∣=r∗(A) ; then the basis E−BE - BE−B of MMM meets E−AE - AE−A in r(E−A)r(E - A)r(E−A) elements; then count. s,t,u,vs, t, u, vs,t,u,v are the sizes of A−BA - BA−B , A∩BA \cap BA∩B , B−AB - AB−A , E−(A∪B)E - (A \cup B)E−(A∪B) . Then t=r∗(A)t = r^*(A)t=r∗(A) , v=r(E−A)v = r(E - A)v=r(E−A) , u+v=∣E∣−∣A∣u + v = |E| - |A|u+v=∣E∣−∣A∣ , t+u=∣B∣=∣E∣−r(M)t + u = |B| = |E| - r(M)t+u=∣B∣=∣E∣−r(M) . Subtracting: t=v+∣A∣−r(M)t = v + |A| - r…

57. [Duality in matroids] Proposition 3.21. MMM is a matroid and eee an element. If eee is not an isthmus, (M−e)∗= ?(M - e)^* = \; ?(M−e)∗=? If eee is not a loop, (M/e)∗= ?(M/e)^* = \; ?(M/e)∗=?

    (M−e)∗=M∗/e\boldsymbol{(M - e)^* = M^*/e}(M−e)∗=M∗/e and (M/e)∗=M∗−e\boldsymbol{(M/e)^* = M^* - e}(M/e)∗=M∗−e Duality swaps deletion and contraction.Example: M=U2,3M = U_{2,3}M=U2,3​ on {a,b,c}\{a, b, c\}{a,b,c} , M∗=U1,3M^* = U_{1,3}M∗=U1,3​ . (M−a)∗=U2,2∗=U0,2=U1,3/a(M - a)^* = U_{2,2}^* = U_{0,2} = U_{1,3}/a(M−a)∗=U2,2∗​=U0,2​=U1,3​/a , and (M/a)∗=U1,2∗=U1,2=U1,3−a(M/a)^* = U_{1,2}^* = U_{1,2} = U_{1,3} - a(M/a)∗=U1,2∗​=U1,2​=U1,3​−a .

58. [Duality in matroids] Why is (M−e)∗=M∗/e(M - e)^* = M^*/e(M−e)∗=M∗/e when eee is not an isthmus of MMM ?

    BBB is a basis of (M−e)∗(M - e)^*(M−e)∗ iff (E−e)−B(E - e) - B(E−e)−B is a basis of MMM avoiding eee iff B∪eB \cup eB∪e is a basis of M∗M^*M∗ iff BBB is a basis of M∗/eM^*/eM∗/e . E−[(E−e)−B]=B∪eE - [(E - e) - B] = B \cup eE−[(E−e)−B]=B∪e . Each step can be reversed.

59. [Duality in matroids] If eee is not an isthmus of a matroid NNN , then (N−e)∗=N∗/e(N - e)^* = N^*/e(N−e)∗=N∗/e .How does this give (M/e)∗=M∗−e(M/e)^* = M^* - e(M/e)∗=M∗−e when eee is not a loop of MMM ?

    Apply it to N=M∗N = M^*N=M∗ , take duals of both sides, and use (M∗)∗=M(M^*)^* = M(M∗)∗=M . Taking duals: N−e=(N∗/e)∗N - e = (N^*/e)^*N−e=(N∗/e)∗ , i.e. M∗−e=(M/e)∗M^* - e = (M/e)^*M∗−e=(M/e)∗ . Since eee is not a loop of MMM , it is not an isthmus of N=M∗N = M^*N=M∗ .

60. [Duality in matroids] Proposition 3.22. How are the loops of a matroid MMM related to M∗M^*M∗ ?

    eee is a loop of MMM iff eee is an isthmus of M∗M^*M∗ . eee is in no basis of MMM iff eee is in every basis complement.Example: MMM on {a,b}\{a, b\}{a,b} with only basis aaa : bbb is a loop of MMM , and M∗M^*M∗ has only basis bbb , so bbb is an isthmus of M∗M^*M∗ .

61. [Duality in matroids] Since eee is an isthmus of MMM iff eee is a loop of M∗M^*M∗ , isthmuses are also called coloops.

62. [Graphic and representable duality] III and DDD are planar drawings of the icosahedron (12 vertices) and the dodecahedron (20 vertices), dual planar graphs with 30 edges each. What are r(M(I))r(M(I))r(M(I)) and r(M(D))r(M(D))r(M(D)) , and how are M(I)M(I)M(I) and M(D)M(D)M(D) related?

    r(M(I))=11\boldsymbol{r(M(I)) = 11}r(M(I))=11 , r(M(D))=19\boldsymbol{r(M(D)) = 19}r(M(D))=19 , and M(I)∗=M(D)M(I)^* = M(D)M(I)∗=M(D) . A spanning tree of a connected graph with vvv vertices has v−1v - 1v−1 edges, and 11+19=3011 + 19 = 3011+19=30 as needed for dual matroids.

63. [Graphic and representable duality] III (icosahedron) and DDD (dodecahedron) are dual planar graphs on the same 30 edges, and M(I)∗=M(D)M(I)^* = M(D)M(I)∗=M(D) .What does M(I)∗=M(D)M(I)^* = M(D)M(I)∗=M(D) say about spanning trees?

    The complement of any spanning tree of DDD is a spanning tree of III . Complement means the set complement in the edge set, not the graph complement. Bases of M∗M^*M∗ are the complements of bases of MMM . Thick: a spanning tree of the dodecahedron. Thin: the complementary dual edges, a spanning tree of the icosahedron.

64. [Graphic and representable duality] GGG is a connected planar graph with dual graph G∗G^*G∗ (one vertex per face, one dual edge crossing each edge), and TTT is a spanning tree of GGG . Why are the dual edges of E−TE - TE−T connected in G∗G^*G∗ , and why are they acyclic?

    Connected because TTT is acyclic; acyclic because TTT is spanning. A cycle of TTT would be needed to separate two faces of GGG . A cycle of dual edges in E−TE - TE−T would be a closed curve with vertices of GGG on both sides and no edge of TTT crossing it, so TTT would not connect all vertices.A careful proof uses the Jordan Curve Theorem.

65. [Graphic and representable duality] Euler's polyhedral formula GGG is a connected planar graph with vvv vertices, eee edges and fff faces, including the unbounded face. Then v−e+f= ?v - e + f = \; ?v−e+f=?

    2\boldsymbol{2}2 Euler found this around 1750, about 180 years before matroids were invented.Example: the cube has 8−12+6=28 - 12 + 6 = 28−12+6=2 .

66. [Graphic and representable duality] How does the matroid proof of Euler's formula v−e+f=2v - e + f = 2v−e+f=2 (connected planar GGG , with dual graph G∗G^*G∗ ) go?

    Compute r(M(G)∗)r(M(G)^*)r(M(G)∗) in two ways: e−v+1e - v + 1e−v+1 and f−1f - 1f−1 . A spanning tree of GGG has v−1v - 1v−1 edges, so its complement, a spanning tree of G∗G^*G∗ , has e−v+1e - v + 1e−v+1 edges. G∗G^*G∗ has fff vertices, so its spanning trees have f−1f - 1f−1 edges. Then e−v+1=f−1e - v + 1 = f - 1e−v+1=f−1 .Example: the icosahedron has 30−12+1=19=20−130 - 12 + 1 = 19 = 20 - 130−12+1=19=20−1 .

67. [Graphic and representable duality] CCC is a circuit of the cycle matroid M(G)M(G)M(G) if and only if CCC is a cycle of the graph GGG .

    This is why M(G)M(G)M(G) is called the cycle matroid.

68. [Graphic and representable duality] What is a cut-set of a connected graph?

    A minimal set of edges whose removal disconnects the graph. Example: in a cycle C4C_4C4​ , any two edges form a cut-set; one edge alone does not disconnect it.

69. [Graphic and representable duality] GGG is a connected graph. Which edge sets are the cocircuits of M(G)M(G)M(G) ?

    The cut-sets of GGG . Cocircuits are the complements of hyperplanes, and a hyperplane of M(G)M(G)M(G) is a maximal set of edges that does not connect all vertices.Example: in C4C_4C4​ , the cocircuits are the 6 pairs of edges.

70. [Graphic and representable duality] What is a cut-vertex of a connected graph?

    A vertex whose removal (together with its incident edges) disconnects the graph. Example: in G2G_2G2​ , the shared vertex vvv of the two triangles is a cut-vertex.

71. [Graphic and representable duality] GGG is a connected graph and vvv is a vertex that is not a cut-vertex. What is the set of edges incident to vvv in M(G)M(G)M(G) ?

    A cocircuit of M(G)M(G)M(G) . The other edges connect all vertices except vvv , so they form a flat of rank r(M(G))−1r(M(G)) - 1r(M(G))−1 (a hyperplane); adding any edge at vvv gives a spanning set. Example: the edges at vertex 1 give the cocircuit {a,f,g,j}\{a, f, g, j\}{a,f,g,j} .

72. [Graphic and representable duality] In this graph GGG , which vertices give 2-element cocircuits of M(G)M(G)M(G) , and what are those cocircuits?

    Vertex 3 gives {b,c}\{b, c\}{b,c} , vertex 6 gives {e,f}\{e, f\}{e,f} . No vertex of GGG is a cut-vertex, so the edges at each vertex form a cocircuit, and only vertices 3 and 6 have degree 2.

73. [Graphic and representable duality] vvv is a cut-vertex of a connected graph GGG . Is the set of edges incident to vvv a cocircuit of M(G)M(G)M(G) ?

    No: it is partitioned into more than one cocircuit. Example: in two triangles sharing the vertex vvv , the 4 edges at vvv form two cocircuits of 2 edges each, one in each triangle.

74. [Graphic and representable duality] What are the size and the rank of M(K5)M(K_5)M(K5​) , and of its dual M(K5)∗M(K_5)^*M(K5​)∗ ?

    M(K5)M(K_5)M(K5​) : 10 points, rank 4. M(K5)∗M(K_5)^*M(K5​)∗ : 10 points, rank 6. A spanning tree of K5K_5K5​ has 4 edges, and 10−4=610 - 4 = 610−4=6 . M(K5)M(K_5)M(K5​) drawn in 3 dimensions: the three-dimensional Desargues configuration.

75. [Graphic and representable duality] Is M(K5)∗M(K_5)^*M(K5​)∗ graphic?

    No. This matches K5K_5K5​ being non-planar: the dual of M(G)M(G)M(G) is graphic only when GGG is planar.

76. [Graphic and representable duality] Suppose M(K5)∗=M(H)M(K_5)^* = M(H)M(K5​)∗=M(H) for a connected graph HHH . How many edges and vertices does HHH have?

    10 edges and 7 vertices. M(K5)∗M(K_5)^*M(K5​)∗ has rank 10−4=610 - 4 = 610−4=6 , so a spanning tree of HHH has 6 edges, so HHH has 7 vertices.

77. [Graphic and representable duality] Suppose M(K5)∗=M(H)M(K_5)^* = M(H)M(K5​)∗=M(H) for a connected graph HHH with 7 vertices and 10 edges.What is the contradiction?

    A vertex of HHH of degree ≤2\le 2≤2 gives a circuit of size ≤2\le 2≤2 in M(K5)M(K_5)M(K5​) , but M(K5)M(K_5)M(K5​) has no circuits smaller than triangles. The average degree in HHH is 20/7<320/7 < 320/7<3 . The edges at that vertex form a cocircuit of M(K5)∗M(K_5)^*M(K5​)∗ , i.e. a circuit of M(K5)M(K_5)M(K5​) . A degree-1 vertex gives an isthmus of M(K5)∗M(K_5)^*M(K5​)∗ , i.e. a loop of M(K5)M(K_5)M(K5​) .

78. [Graphic and representable duality] Why is K5K_5K5​ not planar (by Euler's formula)?

    A connected planar graph without multiple edges has e≤3v−6e \le 3v - 6e≤3v−6 , but K5K_5K5​ has e=10>9e = 10 > 9e=10>9 . Every face is bounded by at least 3 edges and every edge borders 2 faces, so 3f≤2e3f \le 2e3f≤2e . With f=2−v+ef = 2 - v + ef=2−v+e this gives e≤3v−6e \le 3v - 6e≤3v−6 .

79. [Graphic and representable duality] Theorem 3.27 GGG is a connected graph. The dual matroid M(G)∗M(G)^*M(G)∗ is graphic if and only if … ? And then M(G)∗= ?M(G)^* = \; ?M(G)∗=?

    GGG is planar, and then M(G)∗=M(G∗)M(G)^* = M(G^*)M(G)∗=M(G∗) , where G∗G^*G∗ is the dual graph. Example: the complement of a spanning tree of the cube (thick) is a spanning tree of the dual octahedron.

80. [Graphic and representable duality] GGG is a connected planar graph with dual graph G∗G^*G∗ .Why is M(G∗)=M(G)∗M(G^*) = M(G)^*M(G∗)=M(G)∗ ?

    The complements of the spanning trees of GGG are the spanning trees of G∗G^*G∗ , and the bases of M∗M^*M∗ are the complements of the bases of MMM . Example: complementary spanning trees of the octahedron (left) and the cube (right).

81. [Graphic and representable duality] What is Kuratowski's Theorem?

    A graph GGG is planar if and only if it contains neither K5K_5K5​ nor K3,3K_{3,3}K3,3​ as a topological minor. HHH is a topological minor of GGG if HHH is obtained from GGG by removing edges and "removing" vertices of degree 2 (contracting an edge at a vertex of degree 2).

82. [Graphic and representable duality] GGG is a connected graph and M(G)∗M(G)^*M(G)∗ is graphic.How does the outline of the proof show that GGG is planar?

    GGG contains neither K5K_5K5​ nor K3,3K_{3,3}K3,3​ as a topological minor, so GGG is planar by Kuratowski's Theorem. M(K5)∗M(K_5)^*M(K5​)∗ and M(K3,3)∗M(K_{3,3})^*M(K3,3​)∗ are not graphic; showing that a topological minor K5K_5K5​ or K3,3K_{3,3}K3,3​ of GGG would make M(G)∗M(G)^*M(G)∗ non-graphic takes some work.

83. [Graphic and representable duality] When is a matroid MMM cographic?

    When M∗M^*M∗ is graphic. With G\mathcal{G}G the class of graphic matroids: G∗={M∣M∗∈G}\mathcal{G}^* = \{M \mid M^* \in \mathcal{G}\}G∗={M∣M∗∈G} .Example: M(K5)∗M(K_5)^*M(K5​)∗ is cographic, since (M(K5)∗)∗=M(K5)(M(K_5)^*)^* = M(K_5)(M(K5​)∗)∗=M(K5​) is graphic.

84. [Graphic and representable duality] Is M(K5)M(K_5)M(K5​) cographic?

    No. M(K5)M(K_5)M(K5​) cographic would mean M(K5)∗M(K_5)^*M(K5​)∗ graphic, which fails because K5K_5K5​ is not planar.

85. [Graphic and representable duality] G\mathcal{G}G is the class of graphic matroids and G∗\mathcal{G}^*G∗ the class of cographic matroids. What is G∩G∗\mathcal{G} \cap \mathcal{G}^*G∩G∗ ?

    P\boldsymbol{\mathcal{P}}P , the class of cycle matroids of planar graphs. For connected GGG , M(G)M(G)M(G) is cographic exactly when M(G)∗M(G)^*M(G)∗ is graphic, i.e. when GGG is planar.Example: M(K4)∈PM(K_4) \in \mathcal{P}M(K4​)∈P ; M(K5)∈GM(K_5) \in \mathcal{G}M(K5​)∈G but M(K5)∉G∗M(K_5) \notin \mathcal{G}^*M(K5​)∈/G∗ .

86. [Graphic and representable duality] The book's provocative statement: matroids were invented to define duals of non-planar graphs.

    A planar graph GGG has a dual graph G∗G^*G∗ ; every graph GGG has a dual matroid M(G)∗M(G)^*M(G)∗ .

87. [Graphic and representable duality] Is the dual of a representable matroid always representable?

    Yes. In contrast, the dual of a graphic matroid M(G)M(G)M(G) ( GGG connected) is graphic only when GGG is planar.

88. [Graphic and representable duality] Theorem 6.6 MMM is a matroid of rank rrr on nnn points. The matrix A=[ Ir×r∣D ]A = [\,I_{r \times r} \mid D\,]A=[Ir×r​∣D] represents MMM if and only if which matrix represents M∗M^*M∗ ?

    A∗=[ −DT∣I(n−r)×(n−r) ]\boldsymbol{A^* = [\,-D^T \mid I_{(n-r) \times (n-r)}\,]}A∗=[−DT∣I(n−r)×(n−r)​] The columns of I(n−r)×(n−r)I_{(n-r)\times(n-r)}I(n−r)×(n−r)​ in A∗A^*A∗ belong to the complement of the basis that has the identity columns in AAA .Example: A=[101011]A = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}A=[10​01​11​] represents U2,3U_{2,3}U2,3​ , so A∗=[−1−11]A^* = \begin{bmatrix} -1 & -1 & 1 \end{bmatrix}A∗=[−1​−1​1​] represents U2,3∗=U1,3U_{2,3}^* = U_{1,3}U2,3∗​=U1,3​ .

89. [Graphic and representable duality] The matrix below, with columns a,b,c,d,e,f,ga, b, c, d, e, f, ga,b,c,d,e,f,g , represents a rank 4 matroid MMM : A=[100011101001−1−100100100001001]A = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & -1 & -1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 \end{bmatrix}A=⎣⎡​1000​0100​0010​0001​1100​1−110​1−101​⎦⎤​ What matrix A∗A^*A∗ represents M∗M^*M∗ ?

    A∗=[−1−100100−11−10010−110−1001]\boldsymbol{A^* = \begin{bmatrix} -1 & -1 & 0 & 0 & 1 & 0 & 0 \\ -1 & 1 & -1 & 0 & 0 & 1 & 0 \\ -1 & 1 & 0 & -1 & 0 & 0 & 1 \end{bmatrix}}A∗=⎣⎡​−1−1−1​−111​0−10​00−1​100​010​001​⎦⎤​ {a,b,c,d}\{a, b, c, d\}{a,b,c,d} has identity columns in AAA , so the complement {e,f,g}\{e, f, g\}{e,f,g} gets identity columns in A∗A^*A∗ ; the columns of a,b,c,da, b, c, da,b,c,d are −DT-D^T−DT , where DDD is the last three columns of AAA .Multiplying columns by non-zero constants…

90. [Graphic and representable duality] The recipe A=[ I∣D ]↦A∗=[ −DT∣I ]A = [\,I \mid D\,] \mapsto A^* = [\,-D^T \mid I\,]A=[I∣D]↦A∗=[−DT∣I] for a matrix of the dual matroid: which relation holds between the rows of AAA and the rows of A∗A^*A∗ ?

    Every row of AAA is orthogonal to every row of A∗A^*A∗ (dot product 0). Each dot product has either zero or two non-zero terms, ddd and −d-d−d , which cancel.Example: (0,1,0,0,1,−1,−1)⋅(−1,1,0,−1,0,0,1)=1−1=0(0, 1, 0, 0, 1, -1, -1) \cdot (-1, 1, 0, -1, 0, 0, 1) = 1 - 1 = 0(0,1,0,0,1,−1,−1)⋅(−1,1,0,−1,0,0,1)=1−1=0 .

91. [Graphic and representable duality] This rank 4 matroid MMM has the dual M∗M^*M∗ represented by the columns a,…,ga, \dots, ga,…,g of [1−10010011100101101001]\begin{bmatrix} 1 & -1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{bmatrix}⎣⎡​111​−111​010​001​100​010​001​⎦⎤​ Columns ccc and fff are equal. Why does that make sense in MMM ?

    E−{c,f}E - \{c, f\}E−{c,f} is a hyperplane of MMM , so {c,f}\{c, f\}{c,f} is a cocircuit of MMM , i.e. a circuit (double point) of M∗M^*M∗ . The same holds for ddd and ggg . M∗M^*M∗ : the line aebaebaeb and the double points cfcfcf and dgdgdg .

92. [Direct sums and connectivity] M1M_1M1​ and M2M_2M2​ are matroids on disjoint ground sets E1E_1E1​ and E2E_2E2​ . What is the direct sum M1⊕M2M_1 \oplus M_2M1​⊕M2​ ?

    The matroid on E1∪E2E_1 \cup E_2E1​∪E2​ whose independent sets are the sets I1∪I2I_1 \cup I_2I1​∪I2​ with I1I_1I1​ independent in M1M_1M1​ and I2I_2I2​ independent in M2M_2M2​ . Likewise M1⊕⋯⊕MkM_1 \oplus \dots \oplus M_kM1​⊕⋯⊕Mk​ for kkk matroids on disjoint sets. ⊕\oplus⊕ is commutative and associative.Example: U1,1⊕U1,1=U2,2U_{1,1} \oplus U_{1,1} = U_{2,2}U1,1​⊕U1,1​=U2,2​ .

93. [Direct sums and connectivity] M1=U2,4M_1 = U_{2,4}M1​=U2,4​ on {a,b,c,d}\{a, b, c, d\}{a,b,c,d} ; M2M_2M2​ on {e,f,g,h}\{e, f, g, h\}{e,f,g,h} has circuits efg,efh,ghefg, efh, ghefg,efh,gh . Which of {a,c,e}\{a, c, e\}{a,c,e} , {a,b,c}\{a, b, c\}{a,b,c} , {a,e,g,h}\{a, e, g, h\}{a,e,g,h} , {a,b,e,g}\{a, b, e, g\}{a,b,e,g} are independent in M1⊕M2M_1 \oplus M_2M1​⊕M2​ , and what is r(M1⊕M2)r(M_1 \oplus M_2)r(M1​⊕M2​) ?

    Independent: {a,c,e}\{a, c, e\}{a,c,e} and {a,b,e,g}\{a, b, e, g\}{a,b,e,g} . Rank 4. {a,b,c}\{a, b, c\}{a,b,c} is 3 points of the line U2,4U_{2,4}U2,4​ , and {a,e,g,h}\{a, e, g, h\}{a,e,g,h} contains the circuit ghghgh . r(M1⊕M2)=r(M1)+r(M2)=2+2r(M_1 \oplus M_2) = r(M_1) + r(M_2) = 2 + 2r(M1​⊕M2​)=r(M1​)+r(M2​)=2+2 . A drawing of M1⊕M2M_1 \oplus M_2M1​⊕M2​ : the two lines in two different planes, which span rank 4.

94. [Direct sums and connectivity] M1,M2M_1, M_2M1​,M2​ are matroids on disjoint ground sets E1,E2E_1, E_2E1​,E2​ . What are the independent sets, the bases and the rank function of M1⊕M2M_1 \oplus M_2M1​⊕M2​ ?

    Independent sets I1∪I2I_1 \cup I_2I1​∪I2​ with IiI_iIi​ independent in MiM_iMi​ Example: U2,3⊕U1,1U_{2,3} \oplus U_{1,1}U2,3​⊕U1,1​ on {a,b,c}∪{d}\{a, b, c\} \cup \{d\}{a,b,c}∪{d} has the independent set {a,d}\{a, d\}{a,d} . Bases B1∪B2B_1 \cup B_2B1​∪B2​ with BiB_iBi​ a basis of MiM_iMi​ Example: {a,b,d}\{a, b, d\}{a,b,d} in U2,3⊕U1,1U_{2,3} \oplus U_{1,1}U2,3​⊕U1,1​ , so its rank is 2+1=32 + 1 = 32+1=3 . Rank function rM1⊕M2(X)=rM1(X∩E1)+rM2(X∩E2)r_{M_1 \oplus M_2}(X) = r_{M_1}(X \cap E_1) +…

95. [Direct sums and connectivity] M1,M2M_1, M_2M1​,M2​ are matroids on disjoint ground sets E1,E2E_1, E_2E1​,E2​ . What are the flats, the hyperplanes and the spanning sets of M1⊕M2M_1 \oplus M_2M1​⊕M2​ ?

    Flats F1∪F2F_1 \cup F_2F1​∪F2​ with FiF_iFi​ a flat of MiM_iMi​ Example: in U2,3⊕U1,1U_{2,3} \oplus U_{1,1}U2,3​⊕U1,1​ on {a,b,c}∪{d}\{a, b, c\} \cup \{d\}{a,b,c}∪{d} , {a}∪∅\{a\} \cup \emptyset{a}∪∅ is a flat. Hyperplanes H1∪E2H_1 \cup E_2H1​∪E2​ with H1H_1H1​ a hyperplane of M1M_1M1​ , and E1∪H2E_1 \cup H_2E1​∪H2​ with H2H_2H2​ a hyperplane of M2M_2M2​ Example: {a,d}\{a, d\}{a,d} and {a,b,c}\{a, b, c\}{a,b,c} are hyperplanes of U2,3⊕U1,1U_{2,3} \oplus U_{1,1}U2,3​⊕U1,1​ . Spanning sets S1∪S2S…

96. [Direct sums and connectivity] M1,M2M_1, M_2M1​,M2​ are matroids on disjoint ground sets. What are the circuits, the cocircuits and the dual of M1⊕M2M_1 \oplus M_2M1​⊕M2​ ?

    Circuits C(M1)∪C(M2)\mathcal{C}(M_1) \cup \mathcal{C}(M_2)C(M1​)∪C(M2​) : no circuit meets both ground sets Example: U2,3⊕U1,1U_{2,3} \oplus U_{1,1}U2,3​⊕U1,1​ on {a,b,c}∪{d}\{a, b, c\} \cup \{d\}{a,b,c}∪{d} has the single circuit {a,b,c}\{a, b, c\}{a,b,c} . Cocircuits C∗(M1)∪C∗(M2)\mathcal{C}^*(M_1) \cup \mathcal{C}^*(M_2)C∗(M1​)∪C∗(M2​) Example: the cocircuits of U2,3⊕U1,1U_{2,3} \oplus U_{1,1}U2,3​⊕U1,1​ are {b,c},{a,c},{a,b},{d}\{b, c\}, \{a, c\}, \{a, b\}, \{d\}{b,c},{a,c},{a,b},{d} . Dual…

97. [Direct sums and connectivity] H1,H2H_1, H_2H1​,H2​ are hyperplanes of M1,M2M_1, M_2M1​,M2​ (disjoint ground sets E1,E2E_1, E_2E1​,E2​ ). Why is H1∪H2H_1 \cup H_2H1​∪H2​ not a hyperplane of M1⊕M2M_1 \oplus M_2M1​⊕M2​ ?

    r(H1∪H2)=r(M1⊕M2)−2r(H_1 \cup H_2) = r(M_1 \oplus M_2) - 2r(H1​∪H2​)=r(M1​⊕M2​)−2 , one less than a hyperplane needs. The hyperplanes are H1∪E2H_1 \cup E_2H1​∪E2​ and E1∪H2E_1 \cup H_2E1​∪H2​ : a hyperplane of one summand together with the entire other summand.Example: in U2,4⊕U2,4U_{2,4} \oplus U_{2,4}U2,4​⊕U2,4​ on {a,b,c,d}∪{e,f,g,h}\{a, b, c, d\} \cup \{e, f, g, h\}{a,b,c,d}∪{e,f,g,h} (rank 4), {a}∪{e}\{a\} \cup \{e\}{a}∪{e} has rank 2, while {a}∪{e,f,g,h}\{a\} \cup \{e, f, g, h\}{a}∪{e,f,g…

98. [Direct sums and connectivity] MMM is the matroid on {a,b,c,d,e,f,g}\{a, b, c, d, e, f, g\}{a,b,c,d,e,f,g} with circuits ab,ac,bc,def,deg,fgab, ac, bc, def, deg, fgab,ac,bc,def,deg,fg . Write MMM as a direct sum.

    M=U1,3⊕M2\boldsymbol{M = U_{1,3} \oplus M_2}M=U1,3​⊕M2​ : the triple point {a,b,c}\{a, b, c\}{a,b,c} and M2M_2M2​ on {d,e,f,g}\{d, e, f, g\}{d,e,f,g} . M2M_2M2​ is the line with ddd , eee and the double point fgfgfg . No circuit uses points of both {a,b,c}\{a, b, c\}{a,b,c} and {d,e,f,g}\{d, e, f, g\}{d,e,f,g} . Example: {b}∪{e,g}={b,e,g}\{b\} \cup \{e, g\} = \{b, e, g\}{b}∪{e,g}={b,e,g} is a basis of MMM .

99. [Direct sums and connectivity] MMM is a matroid on EEE . Which relation RRR on EEE is used to break MMM into a direct sum?

    xRyx \mathrel{R} yxRy if x=yx = yx=y or some circuit contains both xxx and yyy . Example: with circuits ab,ac,bc,def,deg,fgab, ac, bc, def, deg, fgab,ac,bc,def,deg,fg , the classes of RRR are {a,b,c}\{a, b, c\}{a,b,c} and {d,e,f,g}\{d, e, f, g\}{d,e,f,g} .

100. [Direct sums and connectivity] RRR is the relation on the ground set of a matroid: xRyx \mathrel{R} yxRy if x=yx = yx=y or some circuit contains xxx and yyy . What kind of relation is RRR , and which property is hard to prove?

     An equivalence relation; transitivity is the hard part. Reflexive and symmetric follow from the definition. Transitivity is circuit transitivity, proved with strong circuit elimination.