38th ACCMCC

This year the ACCMCC (“short” for Australasian Conference in Combinatorial Mathematics and Combinatorial Computing) was organised by our own contributor Dillon Mayhew. This gave me the chance to go to beautiful Wellington to see excellent talks and hang out with many Australasian (and not) combinatorialists. Here’s a picture of most of the conference participants, which was taken by Michael Welsh and posted on the conference website.

IMG_0220.JPG

Not only were there many talks focused on matroids, our favourite combinatorial objects were also mentioned in several other talks, a sign of the increasing popularity of matroid theory.

We had nine excellent plenary talks, starting Monday morning with Mike Atkinson, who talked about permutation patterns: permutations may be seen as a set of points in the plane, a setting which gives a natural order on permutations. Then one may look at classes of permutations that are downclosed under this partial order and study the minimal obstructions to membership of a class. One can start with a class and look for the minimal obstructions or start from minimal obstructions and determine the class. Does this sound familiar?

On Monday afternoon the plenary was by another of our bloggers, Stefan van Zwam. Stefan talked about partial fields in disguise, starting by introducing totally unimodular matrices and then moving on to generalisations of this idea (namely, dyadic, near regular, and golden ratio matrices). Stefan presented beautiful results, in terms of representability, excluded minors and decompositions, and then introduced some recent results on fragile matroids. It was a very pleasant tour of important results and open problems in the area.

The Tuesday morning plenary talk was on finite geometry. Simeon Ball talked about sets of lines in affine geometry. These sets of lines had restrictions on them: a Kakeya set of lines has the property that every line has a different direction, while a Bourgain set has few lines on any given plane. The speaker gave results on these types of sets and proofs using a combination of combinatorial methods and algebraic methods, in particular from algebraic geometry.

Tuesday afternoon we got to enjoy a talk by Andrew Thomason on hypergraph containers. These are a powerful tool in studying various combinatorial problems, such as counting $H$-free graphs, sparse arithmetic progressions and so on. The idea is that, instead of dealing with independent sets (i.e. sets of vertices not containing any hyperedge) in a hypergraph – of which there may be exponentially many – we consider these sets, aptly named containers, with the property that each independent set is contained in a container. An amazing theorem shows that in an $r$-uniform hypergraph we can find a relatively small collection of containers, each one not too large. The talk contained a proof of this result, using a prune and build algorithm.

The Wednesday session opened with Sergey Norine, who told us about a recent result on densities of graphs, an analogue of matroid growth rates. Using deep results from the Graph Minor Project, the speaker showed that the density of any minor-closed class of graphs is a rational number. This is proved by showing that one may obtain a sequence of graphs achieving the maximal density by gluing together smaller graphs. This is somewhat in line with the conjecture that the maximum sized matroids in a minor-closed class with linear growth rate may be constructed by sums of a finite set of small rank extremal examples.

Wednesday afternoon was dedicated to the conference excursion, so the next plenary talk was on Thursday morning, when Alice Devillers told us about buildings. This are complicated but very useful objects that were first defined and studied by Jacques Tits. We were given an example of buildings, arising from projective spaces, and then the classical definition, followed by a more modern combinatorial definition. Buildings are very much related to Coxeter groups and are a useful tool when working with algebraic groups.

The Thursday session opened with another matroid talk, by James Oxley. The first result presented in the talk was a chain theorem for internally 4-connected binary matroids. Tutte proved that if a matroid is 3-connected and is not a wheel or a whirl, then there it has an element whose deletion or contraction leaves the matroid 3-connected. Oxley presented the analogous result for internally 4-connected binary matroids. In this case the matroids playing the role of wheels are planar and Möbius triadic ladders and a specific 16 element matroid (the terrahawk). The theorem also involves more than one move, i.e. it is not sufficient to delete or contract one element at the time to maintain internal 4-connectivity, but up to three moves may be required. The second result of the talk was a splitter theorem for internally 4-connected binary matroids. Here some special moves are required to dispose of “bits” of ladders that create complications.

The conference closed on Friday 5 December, after two more excellent plenary talks. In the morning Jaroslav Nešetřil presented a notion of density in graphs that turns out to be extremely effective. Namely, he introduced the dichotomy between nowhere dense graphs and somewhere dense graphs. This dichotomy can be characterised using many invariants, such that independence number, chromatic number, and clique number to name a few.

The last plenary talk of the conference was delivered by Mark Wilson, who talked about multivariate generating functions. While univariate generating functions are well understood, many difficulties arise when dealing with multivariate ones. Hence the need to systematise the theory for of asymptotic coefficient extraction from multivariate generating functions.

I only discussed the plenary talks in this post, but there were lots of really interesting contributed talks as well. I’m certainly looking forward to the next edition of this conference, the 39th ACCMCC, at University of Queensland, 7-11 December 2015.