All the contributors to this blog have been in Princeton, New Jersey within the last few weeks for the 2014 International Workshop on Structure in Graphs and Matroids. This meeting is a descendant of three very successful workshops run by Bert Gerards in Sittard and Maastricht between 2008 and 2012. Although the location has shifted from the Netherlands to the US, a Dutch connection remains, since the 2014 workshop was organised by Rudi Pendavingh and Stefan van Zwam. They both deserve a vote of thanks, for doing a great job and for continuing the tradition; the biennial meeting has become one of the most important fixtures for people interested in the structural theory of matroids and graphs.
In this type of post, I would usually make note of talks that were relevant to the contents of this blog, as well as talks that I found particularly interesting or attractive. That rule is pretty much useless in this case. For obvious reasons, all the talks had connections to matroid theory, and a large number of talks were high-quality presentations about high-quality results. Judging by a number of conversations I have had over the years, there is a feeling that the matroid community (and its relatives) does a better-than-average job of mathematical communication. I don’t think you would have seen much to contradict that belief at this workshop.
It seems as though it has been a good couple of years for matroid and graph research, since a number of people spoke about important new developments, but one such development obviously stands out. Rota’s Conjecture was the outstanding open problem in matroid theory for decades, and its resolution by Jim Geelen, Bert Gerards, and Geoff Whittle is certainly the most significant accomplishment in the field. Geoff gave a talk on one important step in that project. In particular, he talked us through a sketch of the proof that an excluded minor for representability over a finite field must be $f$-connected. That is, if $\mathrm{GF}(q)$ is a finite field, then for every positive integer $k$, there is an integer $n_{q}(k)$ such that whenever $M$ is an excluded minor for $\mathrm{GF}(q)$-representability, and $(A,B)$ is a $k$-separation of $M$, then either $|A|\leq n_{q}(k)$ or $|B|\leq n_{q}(k)$.
Geoff’s talk is complemented by an article in the Notices of the American Mathematical Society. In addition, you can find the slides from many of the conference talks on this page.
Although singling out talks is essentially an impossible task, I will just mention one that I found particularly interesting. Reinhard Diestel reported on work with Sang-Il Oum that provides a meta-theorem about various width parameters. I’ll illustrate the theorem by talking about branch-width and tangles. A branch-decomposition of a matroid or graph is a tree where the non-leaf vertices have degree three, and the leaves are labeled with elements of the ground-set (edge-set). Now each edge of the tree represents a partition of the ground-set into two parts, in other words, a separation. The decomposition has low width if each of those separations has low order. If a matroid does not have low-width branch-decomposition, then we should be able to certify that this is the case. Tangles allow us to do so. A tangle is an orientation of each of the separations of low order. In particular, if we have a tangle, then we have designated a “small” side of each low-order separation. Certain constraints must be satisfied in order for this orientation to be sensible. The most important of these constraints is that three small sides should not cover the entire ground-set between them. Note that in a low-order decomposition, each internal vertex represents a partition of the ground-set into three “small” parts, so a decomposition is a certificate that there can be no tangle, and vice versa. The work by Diestel and Oum generalises these ideas. We choose families of separations, for example the families that might be represented by an internal vertex of a decomposition, and then the theorem guarantees that either there will be a labeled tree where the internal nodes represent members of our chosen families of separations, or else there is some consistent orientation of separations that avoids those families. More details can be found on the arxiv.
At the close of the conference, Stefan extended an invitation to those interested in contributing to this blog, which I will repeat here. If you have an idea for a post, then please get in touch with one of us to discuss it.
Much speculation surrounds the location of the next workshop, two years from now, and multiple suggestions have been made. Expect updates to follow.
