Thomas Zaslavsky (Binghamton)

What I Remember from Baton Rouge

Abstract for the Combinatorics Seminar
2007 April 1 and 8

I attended the excellent matroid theory sessions and some of the structural graph theory talks. There are powerful developments abroad in matroid theory! I'll try to give the flavor.

• My friend Joseph Kung opened the sessions with "Of cabbages and kings", a review of his major classification theorem (with Jeff Kahns) of "universal models" in matroids theory and ideas for extending it. This was a lovely talk that used only 9 cats (I mean, transparencies).

• A talk on "Matroids with every two elements in a 4-element circuit", which sounds silly, turned out to be quite interesting. The graphic such matroids are precisely those of the complete multipartite graphs with at least 4 classes, or with 2 or 3 classes all of size at least 2. The binary and regular matroids of this type were also mentioned. (Talk by Oxley's student Deborah Chun.)

  This talk illustrated a recurrent theme of the close relationship between matroid and graph structure.

• A "clone class" in M is a subset S of the ground set E such that each permutation of E that fixes every element outside S is an automorphism of M. Clones are something recent (by my standard) but important in several ways. Nontrivial clone classes are important in vector representation problems because they lead to projectively inequivalent representations. Elements that can't be cloned in a nontrivial way, called "fixed", are also important.

  Some talks concerned clones, such as "On close sets of GF(q)-representable matroids", presented by James Reid.

• A traditional theme in matroid theory, which only gains vitality with time, is excluded minors. Many talks concerned either excluding an interesting minor and looking at what's left, or finding excluded minors for an interesting property.

  One that caught my attention was "Binary matroids with no M(K_3,3) minor". Dillon Mayhew reported on a 100-page proof that these matroids are

  1. cographic matroids,
  2. certain one-point extensions M*(G)+e₀ of bond matroids of graphs, where G = SM_k, the square Möbius ladder, or TM_k, the triangular Möbius ladder (these are my names), and
  3. 18 sporadic examples, not described in the talk.

  I (and Dan Slilaty) noticed that, since M = M*(G)+e₀) is dual to the coextension M(G)×e₀, M* is the complete lift matroid L₀(Σ) of a signed graph. Furthermore, we can find this signed graph explicitly by projective-planar duality. Perhaps this will lead to a simpler proof?

• Another forbidden minors talk, in the graph theory session, showed again how close graph and matroid theory are. Carolyn Chun spoke on "Unavoidable minors of infinite graphs and matroids". I missed it because it conflicted with the matroid talk by Deborah Chun.

• One difficulty about matroids is that even small ones are so complicated, and so numerous. Actually, no one knows exactly how numerous. In "Matroids with 9 elements", Gordon Royle described a data base, accessible from Royle's Web site, that contains (in the sense that it generates them on the fly, without duplication) all matroids (that is, isomorphism types) of up to 9 points along with various commonly interesting properties, such as, whether they are uniform, or (co)graphic, or binary, and which matroids are 1-point extensions or coextensions of which others. The number of matroids on 9 points of rank 4 is 190214.

  The solution to excluding M(K_3,3) was suggested by noticing subtle patterns in a search of the data base for up to 9 points.

• Another broad theme at the session was "chain theorems", which state that a matroid M of some type contains a small set S of, say, 1, 2, or 3 points such that M/S is again of the same type, or else M belongs to an identifiable minimal set. [The classical examples are that a 3-connected graph contains e such that M/e or M\e is 3-connected, or it is a wheel, and that a 3-connected matroid contains e such that M/e or M\e is 3-connected, or it is a wheel or whirl matroid (Tutte). Indeed, one can specify a 3-connected minor N of M that is to be a minor of M/e or M\e (Seymour).]

  "Inductions for '4-connected' graphs and matroids", delivered by Xiangqian Zhou, and "Chain-type and splitter-type theorems for cocircuits and hyperplanes in 3-connected matroids", by Rhiannon Hall, presented the philosophy and examples of such theorems. "On minor-minimally 3-connected binary matroids" by Loni Delaplane et al. also used a chain theorem.

  There was also a chain talk in the graph theory session: "Chain theorems for 4-prime graphs" by Sang-il Oum, which I couldn't attend.

• Rudi Pendavingh, from Holland, explained "Partial fields and matroids with several inequivalent representations over GF(5)". He exlained partial fields, which combine groups and rings and which I understood for the first time, and applied a theory of "fundamental" elements of partial fields to easily obtain strong old and new results on vector representability. Unfortunately, it appears that the method is very sensitive to the details of the (partial) fields and may not be easy to apply often. Nevertheless, the talk was outstanding.

• Then there were the signed graph talks. (My baby!)
  • I gave a long lecture, "Other matroids from graphs", mostly on some of the many aspects of the frame and lift matroids of signed, gain, and biased graphs, followed by our former student Dan Slilaty on "Signed-graphic matroids".

    My talk was a very fast survey, omitting 2/3 to 3/4 of the subject. (I may give a short version in the seminar, later.)

    Dan's talk was about when the frame matroid G(Σ) of a signed graph is binary (representable over GF(2)) or quaternary (over GF(4)). (This extends the unpublished work of my former student Steve Pagano that assumed 3-connectedness.)

  • In the graph theory session, Bertrand Guenin described work in progress about "When do two graphs have the same even cycles?", which means two graphs with the same binary cycle space, signed in such a way that the negative binary cycles are the same in both. (Guenin belongs to the school that says "even" for positive and "odd" for negative.) I noticed that this work will be the major part of deciding when two signed graphs have the same lift matroid, which is a very hard problem.

  • There is an area of polyhedral-combinatorics optimization that studies "binary clutters". A binary clutter is the set C(M,σ) of negative circuits in a signed binary matroid (M,σ). If the matroid is graphic, it is the set of negative circles in a signed graph. The relevant matroid is the complete lift matroid, L₀(M,σ). A main problem is whether the incidence matrix, as the coefficient matrix A of a linear programming problem constrained by Ax ≥ 1, x ≥ 0, gives integral solutions. (This means a certain polyhedron has integral vertices. Please forgive errors; I don't know enough to state all this correctly.)

    Xujin Chen talked about "An excluded minor characterization of box-Mengerian matroid ports". In a matroid with distinguished element e₀, a "port" is C\e₀ where C is any circuit that contains e₀. (M,σ) is box Mengerian if any linear program whose coefficient matrix is the incidence matrix A of C(M,σ) has an integral dual solution, given an integral objective function (this matrix is called a "TDI" matrix), even when constrained by arbitrary integral upper and lower bounds (that's called "box TDI"). This property depends on L₀(M,σ)'s not having certain forbidden minors, thus on (M,σ)'s not having certain forbidden signed minors.

    Guoli Ding, from L.S.U., also talked about box TDI and binary clutters, but his talk was called "On Quasi-bipartite Graphs". Take A = the unoriented incidence matrix of a graph G. (This is an oriented incidence matrix of −G, i.e., G with all negative edges.) G is "quasi-bipartite" if the polyhedron Ax ≥ 1, x ≥ 0 has integral solutions. Graph theoretically, G is quasi-bipartite iff deleting any odd circle leaves at least one isolated vertex.

• The Strong Perfect Graph Theorem, recently proved after 40 years of effort, says that a graph is perfect (every induced subgraph has chromatic number equal to clique number) if and only if no induced subgraph is an odd C_n or its complement. In "Even pairs in perfect graphs", Maria Chudnovsky (one of the provers) described how the last, and nastiest, 50 pages of the 200-page proof can be replaced by a more elegant argument involving "even pairs" of vertices, i.e., where every induced path between the vertices has even length. (This is not the easiest math to understand, but it's a good improvement of the proof.)

• In the structural graph theory session, Paul Seymour explained how to show there are exponentially many "Perfect matchings in planar cubic graphs", if there are any at all. Sadly, the nice proof methods all failed, so they had to get their hands very dirty—but cleverly so.

• And Neil Robertson spoke "On the S. B. Rao well-quasi-order conjecture", about well-quasiordering of degree sequences (!), which is not yet proved.