The black swan is the emblem of Western Australia – but it seems a little odd that, on the State coat of arms, there is a picture of one being cooked in a large pot of water by two kangaroos …
Tomorrow we will be taking another wildflower walk, so perhaps there will be some final comments on the WA wildflowers in the final episode of this series.
Meanwhile, back in the mathematical universe …
This week, the same seed fund that paid for our visit here brought several colleagues over from Monash, and we have had a week-long workshop. For the first three days, we each presented a short talk, mostly with emphasis on open problems; we ended with a problem session. John Bamberg has reported on this on SymOmega, where most of the slides can be found.
As John explained, the meeting has been given the name MUSIC (acronym for Monash–UWA Symposium In Combinatorics). I like the word “symposium”: it literally means a drinking meeting, but even if you don’t drink, it has the suggestion of a meeting of friends, which certainly has been true of this workshop. Long may it continue!
Here are some random jottings from the week.
At a certain moment, Graham Farr remarked that the chromatic polynomial of the Fano matroid, evaluated at −1, is 30. I know a bit about the chromatic polynomial of a graph; when evaluated at −1, it gives (up to sign) the number of acyclic orientations of the graph. I have no idea what it means for a (binary) matroid. Graham asked what the number 30 meant in terms of the Fano plane. I said, it is the number of point-labellings of the plane, or the number of ways of drawing a Fano plane on a set of seven points. These two descriptions are clearly equivalent, but it was immediately clear that some people understood it better in one form, some in the other. Are there two kinds of combinatorialist, then? I have no idea whether this observation is more than coincidence. As an exercise for the reader, what does the number 24 mean in terms of the Fano plane?
The company spent some time discussing Agrawal’s conjecture, which had been posed by Rosemary and which I described here recently. Here is an interesting sidelight on this. Rosemary challenged us with two special cases, Hadamard designs and projective planes. In general, the problem has a formulation in terms of derangements (permutations with no fixed points), which is particularly clear for projective planes, as follows. This description of the problem was found by Rosemary years ago, and is Problem 38 on my Queen Mary homepage problems.
If π is a projective plane and L a line of π, let A be the affine plane with L as line at infinity. If q is the order of π, then A has q2 points, and q(q+1) lines, falling into q+1 parallel classes (corresponding to the points of L).
Given any affine plane of order q > 2, can we choose for each point x a permutation px of the set of parallel classes such that
- each permutation px is a derangement;
- for x and y distinct points, the permutations px and py disagree on the parallel class containing the line xy?
It follows from the second condition that the permutations px are all distinct. For q = 2, there are four points and only two derangements, giving a “proof” (not involving playing Sudoku) that the construction is not possible. For q = 3, there are nine points and nine derangements, so it is not impossible; and indeed, making a couple of choices without loss of generality, the solution is unique. For larger q, the number of derangements grows much faster than q2, suggesting that solutions will become easier to find (though we failed to find a general method!).
It would be remiss of me not to mention John Bamberg’s talk on the big problems in finite geometry. He didn’t claim that they were the biggest problems; indeed, he said he deliberately left out what he considered the biggest problem, since it is not easy to state. But apart from that, he discussed the prime-power and prime order conjectures, ovoids, generalised polygons, unitals, k-blocking sets, maximal arcs, and k-arcs.
I do worry sometimes that current pressures to publish may deter younger researchers from tackling the big problems. John seems immune from these pressures!
Gordon Royle told us what seemed a remarkable fact about flow polynomials of cubic graphs. Let φ = (1+√5)/2. Then, if G is cubic,
|FG(φ+2)| ≤ φE(G)FG(φ+1)2,
and it is conjectured that equality holds if and only if G is planar. Gordon showed computational evidence that the ratio of the right-hand side to the left-hand side is 1 for planar graphs; the next smallest value of the ratio is 9+18/√5, for a large group of cubic graphs; then another group realise the next ratio, and so on. Fascinating, but further thought showed that it was not as dramatic as it appeared.
There was some time for Kerri Morgan, Graham Farr and me to discuss our work on algebraic properties of chromatic roots (realisability, splitting fields, Galois groups, etc.) More on this sometime, I hope.
There was much much more, but that is enough for now.