Week 4: Chapter 9 (Binary Matroids)

Pre-Notes

• What was really interesting about this chapter is that it proposed certain questions that were unsolved and it was the first time the book has mentioned computational complexity, outlined by this independence oracle (9.4.15). Because we can’t find a polynomial time algorithm to determine whether a matroid presented is binary, we instead look at whether a matroid presented by an independence oracle is graphic. We also need to show that independence and rank oracles are polynomial equivalent.
• A short chapter. Next, we cover Excluded-Minor Theorems
• I read this chapter twice, and wrote up notes after the 2nd time, so they’re a lot less intense than the notes in my text.

Notes

• Binary matroids : matroids that have no U_{2,4} minor
• Two types of theorems:
  • Cardinality of circuit-cocircuit intersections
  • Symmetric differences of circuits
• Symmetric difference is defined as X \triangle Y, which is (X - Y) \cup (Y - X). It is both commutative and associative.
• Theorem 9.1.1: If e is an element of an independent set I of a matroid M, then M has a cocircuit C’ s.t. C’ \cap I = {e}.
• For a matroid M, these statements are equivalent:
  • M is binary
  • If C is a circuit and C’ is a cocircuit, then {C \cap C’} is even.
  • If C_1 and C_2 are distinct circuits, then C_1 \triangle C_2 contains a circuit.
  • If C_1 and C_2 are circuits, then C_1 \triangle C_2 is a disjoint union of circuits.
  • The symmetric difference of any set (1) is either empty (2) contains a circuit
  • The symmetric difference of any set of circuits is a disjoint union of circuits.
  • If B is a basis and C is a circuit, then C = \triangle_{e \in C- B} C(e, B)
  • M has a basis B s.t. if C is a circuit, then C = \triangle_{e \in C - B} C(e, B)
• The proof starts by assuming (iii) is true. It concludes (ii) implies (iii), etc.
• In Theorem 9.1.3, they say if C is a circuit and C’ is a cocircuit, then |C \cap C’| \neq 3, but we expect this as we previously said it had to be even..
• Theorem 9.1.4: A rank r-matroid M is binary iff every rank (r - 2) flat of M is contained in at most three hyperplanes.
• Scum Theorem (see Oxley 1988)
• Tutte’s Theory of chain groups
• The circuit space and cocircuit space of M are the subspaces of V(n, 2) that are generated by the incidence vectors of the circuits and cocircuits, respectively of M.
• 9.3 goes over how 3 sums in graphs are extended to binary matroids. The graph operation of 2 sum is a special case of the clique-sum of operation. How does this extend to n-sum?
• Clique Sum: Take two graphs (say, G_1 and G_2) and stick them along a common subgraph, and then delete all identified edges. There’s a pretty good diagram in section 9.3.
• Generalisation of direct sum and two-sum:
  • Let M_1 and M_2 be binary matroids. If E(M_1) \cap E(M_2) = \null, then M_1 \triangle M_2 = M_1 \oplus M_2.
  • If E(M_1) \cap E(M_2) = {p} and neither M_1 nor M_2 contain p as a loop or a coloop, then M_1 \triangle M_2 = M_1 \oplus_2 M_2.
• 3 sum: When both |E(M_1)| and |(M_2)| exceed six and neither M_1 nor M_2 has a cocircuit contained in T (a set that is a triangle of both), we call M_1 \triangle M_2 the 3-sum, M_1 \oplus_3 M_2 of M_1 and M_2.
• 9.3.3: Let M_1 and M_2 be binary matroids s.t. E(M_1) \cap E(M_2) = T, where T is a triangle of both M_1 and M_2. Then C(M_1 \triangle M_2) is the union of C(M_1 \ T), C(M_2 \ T), and the collection of minimal sets of the form C_1 \triangle C_2 where C_i is a circuit of M_i, s.t. C_1 \cap T = C_2 \cap T and the last set has one element exactly.
• A 3-connected matroid M is the three sum of binary matroids M_1 and M_2 has minors that are isomorphic to each of M_1 and M_2 (9.3.5)
• For an n-element binary matroid:
  • E(M) can be partitioned into circuits
  • Every cocircuit of M has even cardinality (unsurprising)
  • M’ is a binary affine matroid
  • The n-tuple of all ones is in the circuit space of M.
• paper by Welsh (1976) for d(M) the number of sets and b(M) the number of bases (see 9.4.8). On average, a matroid has more bases than circuits. Details beyond scope of book.
• For the bridge graph and avoidance graph, is this or is it not related to say, forbidden graphs? Avoidance graphs and work discussed are due to Bixby and Cunningham (1979), Mighton (2008) and Wagner (2010)
• A matroid is graphic if for eery three distinct cocircuits having a common element (exactly one common element), one of the cocircuits separates the other two.

Other Notes

Two things that seem to be unsolved (but I did not check in to whether they still are?):

• There is no such polynomial time algorithm to test whether a matroid is binary
• The constant in the rank-r simple binary matroid M having no coloops (i.e. \frac{6}{19}) doesn’t seem to satisfy Oxley in terms of being the best possible. Is this still the case?

Readings

• Tutte W. T. “An Algorithm for Determining Whether a Given Binary Matroid is Graphic link
• Qu Z. “On Tutte’s Algorithm for Recognising Binary Graphic Matroids”, link
• Bonus paper I found in the bib of the Tutte paper: Tutte, W. T. “A class of Abelian Groups”