Week 4: Chapter 10 (Excluded Minor Theorems)

Pre-Notes

• In this chapter, they prove the ternary matroid result. Interestingly, I found out today that we’re using a mix of Oxley, Schrijver and some others for our class, and the chapter starts by mentioning the Schrijver book, which focuses on bridging the gap to show the relationship between things like polytopes, linear programming and convex optimisation.
• I’m probably just going to make it through the Truemper paper tonight. The Truemper paper is pretty easy to find. The Ingleton one was paywalled for me. I might check back to see if it’s just an institutional thing, but it didn’t look so, which kind of sucked (wonk wonk) as I’d like to read it!

Main Notes from Chapter

• The field over which we view a totally unimodular matrix does not result in a difference in representation of the matroid.
• Tutte’s original proof of excluded-minor characterisation was long and difficult (1958). Seymour (1980) proposed an alternative one that is constructive. Gerards’ (1989) is the one discussed in this chapter.
• A matroid is regular iff it has no minor isomorphic to U_{2,4}, F_7 or F^{*}_{7}.
• If D is a matrix, then D# is the matrix obtained from replacing every non-zero entry by a one from D. Then we let Y be a (0,1) matrix. A signing of Y is a real matrix Z having every entry in {0, 1, -1} s.t. Z# = Y. So every signing of Y can be obtained from Y by changing some of its entries from 1 to -1.
• For a (0,1) matrix [I_r|X]:
  • X has no totally uni modular signing
  • When viewed over GF(2), the matrix [I_r|X] can be transformed into [I_3|X_F] or [I_4|X^{T}_{F}] by a sequence of (1) deleting rows or columns (2) permuting rows or columns (3) pivoting.
• We demonstrate a proof of the above lemma by using a simple bipartite graph associated with a (0,1) matrix X. The following lemma proves that G has properties s.t. when two distinct vertices from the same vertex class are deleted, a disconnected graph results. This tells us that G is either a path or a cycle. Proof by contradiction.
• Lemma (10.1.6): Let D be an n x n matrix [d_{ij}] with entries in {0, 1, -1}. If G(D#) is a cycle, then D is totally unimodular iff the number of negative entries in D is congruent to n modulo 2.
• The idea for the proof is that if we permute rows and columns, we can transform D -> D_1. We expect that after we permute, our submatrix D’ has a determinant in {0, 1, -1}, which tells us that D is unimodular.
• Camion (1963): Let D_1 and D_2 be totally unimodular matrices. If D^{#}_{1} = D^{#}_{2}, then D_2 can be obtained from D_1 by multiplying some rows and columns by -1.
• For the proof of Lemma 10.1.8, it is shown that a pivot in D_3 produces another matrix (in block diagonal form). This is enough to conclude that G(A^{#}_{1) is disconnected.
• We can generalise our excluded minor characterisation of ternary matroids (Lovász and Schrijver (in Gerards 1989)). The approach used in the book draws from Truemper (1992).
• A matroid is ternary iff it has no minor isomorphic to U_{2,5}, U_{3,5}, F_{7} or F^{*}_{7}. Federico spoke quite a bit about this in the videos.
• If G(X) is a path or a cycle, then N is ternary (Lemma 10.2.2). Proof shows that if N’ is a wheel or a whirl, N’ and therefore N is ternary.
• Violating sub matrices; interestingly, the first resource that came up when I looked this up was one involving circuits and thresholds. I found a Truemper paper that is more helpful.
• In the section characterising graphic matroids, follows from Federico’s lectures. A matroid is graphic iff it has no minor isomorphic to any of the matroids U_{2,4}, F_{7}, F^{*}_{7}, M^{*}(K_5) and M^{*}(K_{3,3}) (basically all the evil graphs). A binary matroid is graphic iff it has no minor isomorphic to F_{7}, F^{*}_{7}, M^{*}(K_5), M^{*}(K_{}3,3). Fano and all those evil graphs.
• The graft matroid.
• Series switch (interchanging labels on edges of a series couple).
• Let M be a 3 connected binary non-graphic matroid having an element e s.t. M \ e is graphic and 3 connected up to series couples but M \ e is not 3 connected. Then:
  • M is isomorphic to F^{*}_{7} or M^{*}(K_5)
  • M* \cong M_1 \oplus_3 M(K_5) for some cographic matroid M_1
  • M has a triad that contains e and some element f for which M / f is non-graphic.
• The section also gets very “only fans” with lemmas about feet.
• The graft (G, \gamma) is isomorphic to either a 3-spoked wheel in which every vertex is coloured or to a 4 spoked wheel in which every vertex other than the hub is coloured.
• A matroid is singable iff it is regular.
• A matroid is transversal iff all of its series minors are transversal (proof due to Piff (1972).
• Finally… These statements are equivalent for a matroid M:
  • M is a graphic gammoid
  • M is a regular gammoid
  • M is a binary gammoid
  • M has no minor isomorphic to U_{2, 4} or M(K_4)
  • M is a direct sum of series parallel networks
• Ingleton (1977) noted that there are infinitely many minor minimal non gammoids and infinitely many series minor minimal non transversal matroids.
• I noticed hilariously that the book not only has notation, but a whole section called “Some interesting matroids”. Something about this feels like I am taking an origami class.

Readings

• Truemper K., “A Decomposition Theory for Matroids. VII. Analysis of Minimal Violation Matrices” (1992) (complete)
• Ingleton, A.W. (1977), “Transversal Matroids and Related Structures”