ACCMCC, Days 4 and 5

Penny Haxell opened proceedings on Thursday with her astonishing work with Ron Aharoni. They give a sufficient condition for a tripartite 3-uniform hypergraph (one whose vertex set is partitioned into three parts so that each hyperedge contains one vertex from each part) has a large matching (set of pairwise disjoint edges). In general, if the hypergraph is regular, then there is a matching of size at least n/2, where n is the size of each part. The Pasch configuration and variants of it show that this is best possible in general.

The idea is that for regular bipartite graphs the result follows from Hall’s marriage theorem. For a tripartite 3-hypergraph, we need to be able to show that the link of a vertex (the bipartite graph induced on its “neighbours”) is suitably “large”. This is done by a somewhat complicated topological property, which for a simplicial complex involves beiung able to extend a function on the boundary of a simplex to the whole simplex. This is applied to the matching complex of the link graph. It is complicated to evaluate, and is not even monotone! So adding an edge to a hypergraph, which clearly cannot reduce the size of a matching, can mess up the proof using this topological parameter.

As we left the room, I was thinking that a Latin square can be represented as a regular tripartite 3-hypergraph (the vertices being the sets of rows, columns, and symbols, and the edges corresponding to the cells), and a matching is a partial transversal; I was wondering whether these methods could give anything on the Ryser and Brualdi conjectures. So I asked Ian Wanless, who assured me that it could not. But we were on the way to a talk by Darcy Best (a student of Ian’s), who told us all about these and some new information about them. (In brief, Ryser’s conjecture, or the part still open, asserts that a Latin square of odd order has a transversal; Brualdi’s conjecture asserts that any Latin square has a partial transversal which is only one short of complete.)

Then Ranjie Mo, a student of Graham Farr and Kerri Morgan, told us about his work on certificates of “Tutte equivalence” of graphs. (Two graphs are Tutte equivalent if they have the same Tutte polynomial.)

This was followed by a really beautiful talk by Graham Farr, on the history of the Tutte–Whitney polynomials. He extolled the benefits of reading the work of the masters (with which I totally agree), and said quite a bit about the very different styles of Whitney and Tutte: while Whitney was prepared to prove an induction step for i = 2, and state that the extension to arbitrary i is immediate, Tutte was extremely precise and careful. He also mentioned a curious extension of the 4-colour theorem. A planar graph G has a dual G*, such that T(G*;x,y) = T(G;y,x). The extension asks: Is it true that, if G is a graph for which there exists a graph G* satisfying the above relation, then G is 4-colourable? (The hypothesis does not force G to be planar; Whitney gives a 7-vertex counterexample.)

After lunch, Jonathan Jedwab gave his conference talk. He started by describing his addiction to the game 2048, and then his idea that other combinatorial construction problems could be turned into similar games; a game-player’s intuition may succeed in a construction where simple fiddling round on a piece of paper does not. He had applied this to finding “suitable cores” and sequences of permutations containing no subsequence whose product is the identity. The computer, behind the scenes, checks the rules in each case and gives feedback on whether a move is legal or, if not, why not.

John Bamberg gave a lovely talk on an attempt to extend Sherk’s theorem (a characterisation of finite affine planes) to Bruck nets. He had also been reading the masters, in this case Bachmann’s book. His take-home soundbite was “A Euclidean plane is an affine plane with a perpendicularity relation”.

I next heard a talk by Ben Burton, one of three on use of combinatorics and computers in topology. A lovely talk, in which the word “slums” was never mentioned! The problem is that you have two triangulations and you want to know if they represent the same topological space. It is computationally hard to decide whether you can reduce one triangulation to the other by moves which monotonically make it smaller. But they are developing computational tools to use on such problems.

Petr Vojtěchovský talked about characterisations of certain varieties of quasigroups (Latin squares under a different umbrella), and in particular, representing certain quasigroups in terms of automorphisms of other, more structured, quasigroups, such as groups. I was quite delighted that Ian Macdonald’s formula for the generating function of the number of conjugacy classes in GLn(p) cropped up in the talk. (But this is my former Queen Mary colleague Ian G. Macdonald, not the Ian D. Macdonald who taught me group theory at the University of Queensland 50 years ago.)

Then into town for the conference dinner at Stamford Plaza. The river is the heart of Brisbane; we went into town and came home on the City Cat, and from the ballroom we could see the lights on the Story Bridge.

Friday started with a beautiful survey by Catherine Greenhill on sampling and counting using Markov chains, and in particular the coupling and canonical paths techniques for showing rapid mixing. This reminded me of an old problem of mine, which I will discuss in a forthcoming post.

There were three contributed sessions before lunch, and I heard three really nice talks. Nick Wormald described the current state of the art in uniform generation of random regular graphs, and in particular, the problem of turning theoretical results into actual programs.

Jeanette McLeod talked about a theorem she proved with Brendan McKay. She defined two notions of switching: one for directed graphs, in which you are allowed to reverse the edges on any set of vertices; the other on 2-edge-coloured graphs, where you are allowed to reverse the colours on the edges on any set of vertices. They want to find the graphs whose isomorphism types are fixed by all switchings. There are two other boolean “switches”, which gave altogether eight problems, all of which they had solved.

In this context, the original Seidel switching corresponds to switching of a 2-edge-colouring of a complete graph. This is not stable if the number of vertices is greater than 3. But the icosahedron corresponds to a situation where there are only two isomorphism classes (up to interchange of colours). There is probablyt something worth investigating here.

Finally, Gabriel Verret talked about a theorem with Pablo Spiga, inspired by the synchronization program. Which (directed) graphs with vertex-primitive automorphism groups have a pair of vertices whose neighbourhoods are (nearly) equal? He answered a problem that had stumped us, though we later got around it another way. But the results they are now working on should certainly have further applications to synchronization.

And so the conference ended, with something of a whimper – people drifted away, and that was that. A very nice conference, and as I hope my write-up indicates, it got better as it went along.


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events and tagged , , , , , , . Bookmark the permalink.

One Response to ACCMCC, Days 4 and 5

  1. A Diabolic Magic Square has the additional property of the magic sum along each of its broken diagonals. Curiously, we can construct a Diabolic Magic Square from a Graeco Latin Square! Read more about it on my blog:

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s