I’ve just spent a week at the 35th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing at Monash University in Clayton, a suburb of Melbourne.
The conference happened to coincide with a research visit to Monash, about which I will say more later. It was organised by Ian Wanless and his team, and was a very successful meeting.
I will just list some of the many things I learned at the conference.
The best plenary talk, in my opinion, was by Petr Vojtěchovský, on Computational aspects of loop theory. Among the things he told us were:
- Lagrange’s Theorem for groups states that the order of a subgroup of a finite group divides the order of the group. The proof is standard fare for a first undergraduate group theory course. It is also true for Moufang loops, though the proof requires the Classification of Finite Simple Groups; for the closely related class of Bol loops, it is unknown whether it holds or not. (These two classes of loops are defined by identities which are weaker versions of the associative law.)
- The mapping group of a loop is the group generated by the left and right translations, and the inner mapping group is the stabiliser of the identity in the mapping group. In a group, but not in a general loop, the inner mappings consist of automorphisms (they are the inner automorphisms, hence the name.) So one could consider the interesting class of automorphic loops, those whose inner mappings are loop automorphisms. Again using the Classification of Finite Simple Groups, it is known that there is no simple automorphic loop (which is not a group) having order less than 2500; but it is not known if this is true in general.
- Moufang and Bol loops with inner mapping group abelian have central nilpotency class at most 3. The proofs are triumphs of automated reasoning, having been found by computer and involving thousands of statements covering hundreds of pages.
Patric Östergård told us that he had successfully counted the Hamiltonian cycles (aka Gray codes) in the 6-dimensional cube: this means that the 26 binary strings of length 6 are ordered in a cycle so that each differs from its neighbour in just one bit. This is a classical problem, mentioned by such luminaries as Donald Knuth and Martin Gardner. The answer is a 23-digit number beginning 358… In a gentle dig at Brendan McKay, who was chairing the talk and is well known for his work on debunking the Bible codes, Patric remarked that 358 is the international dialling code for Finland, his home country. Brendan remarked that he must have made a mistake, and the true number should begin 61…
Jerzy Filar gave a new heuristic for finding Hamiltonian cycles which is claimed to out-perform existing heuristics by a considerable margin. It goes by the descriptive name “snakes and ladders”.
In a little bit of historical revisionism, Johann Makowsky pointed out that the proof by Jaeger, Vertigan and Welsh that evaluating the Tutte polynomial is #P-hard except at special points and curves in the plane is defective: the computational model used is that of Turing, but to declare that a computation of a value at a non-computable real number has a certain complexity requires a different model (the Blum–Shub–Smale model) treating a real number as a black box.
There was also some historical revisionism in the talks on real-representable matroids by Geoff Whittle and Mike Newman, but I have discussed this elsewhere. Incidentally, Mike described himself as “the other Mike Newman”, but both Mike Newmans are co-authors of mine.
János Barát talked about a charming problem. You are given a n×n×n cube made up of n3 small cubes. You wish to dismantle it; at each move you are allowed to remove a cube which has precisely three neighbours (cubes sharing a face with it). You might like to find the simple geometric proof that at least n2 cubes remain after you have made all the moves you can.
There were several talks by locals about the chromatic polynomial, which I will discuss later. The final talk of the conference was by Ian Wanless, about counting subsquares of Latin squares. He challenged me to find an upper bound for the number of subsquares of order 4; that night, since the traffic on the Princes Highway was particularly noisy, I succeeded in doing that.
The conference excursion was to two wineries (Killara and Yering), where we got a very good lunch at Killara, and several wines to taste, some remarkably good, some not so good. Afterwards, we had a short walk in the Dandenong forest (not long enough for my liking), where we saw no lyrebirds, but several other birds put in an appearance, including those above, and the ubiquitous galahs.