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 2^{6} 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 n^{3} 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 n^{2} 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.
Sounds like a fascinating conference Peter but for me the highlight would have been the walks and especially seeing the Sulpher Crested Cockatoos in the wild!
“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.”
Which kind of bound did you find?
The number of subsquares of order 4 is at most n^{2}(n−1)(n−2)/96, with equality for n>4 if and only if the Latin square is the Cayley table of an elementary abelian 2-group.
That’s a very nice and clean result! Does the method work for larger orders as well?
Not obviously; but we hope to think about that this week. Another question Ian is keen to look at is, how many can you have if n is not a power of 2.
The plenary speakers’ slides are now available from the conference web page: http://users.monash.edu.au/~accmcc/
Looking at our paper, we obtained the bound n^2(n-1)(n-2)/2 in the 4×4 case, so that’s a considerable improvement.
Observation: for all n, we can always embed an elementary abelian 2-group of order >n/4 in a Latin square of order n. The maximum number of 4×4 subsquares is thus Theta(n^4).
Another (semi-random) observation: if we take a Latin square of order n with many 2×2 subsquares (or 4x4s, or 8x8s, etc.) and take the direct product with (Z_2)^m, we get a Latin square of order n*2^m that should have lots of 4×4 subsquares. I’m not sure how useful this observation is, but perhaps it gives a reasonable number for orders e.g. 5*2^m.
Hmm… I’m guessing your proof was: The total number of 4×4 subsquares is =4×4 then stop. Else we add in another cell (x,y) with the same symbol as (i,j). Every subsquare now should be at least 4×4. In the worse case, we will have found (n-1)(n-2) 4×4 subsquares, but they will have all been isotopic to Z_2^2 (so would have been counted 6 times each). [There’d be a bit of bookkeeping to account for the subsquares isotopic to the Z_4’s, but it wouldn’t be too bad.] If this is the proof, then it seems like it should generalise to larger kxk subsquares, but looks like it might be a bookkeeping nightmare.
We have generalised it to subsquares of any 2-power order. The result is what you expect: the number of subsquares is at most the number in an elementary abelian 2-group of order n (if you pretend for a moment that such a thing can exist), with equality if and only if you really do have an elementary abelian 2-group.
Hope this is not too unclear…
Now published in J. Combinatorial Theory (A) 124 (2014), 41-56. The doi is
10.1016/j.jcta.2014.01.002
Pingback: Problem of the week 2 | a mathematical mote