I know I’m not going to be able to keep this up, but I felt I needed to report on the first day of what is turning out to be an excellent conference at the National University of Singapore. This will leave me with the issue that my reporting of subsequent talks in this conference will not be at the same degree as I will present here, even though they might be of the same standard. So I apologise in advance.
First of all, we kicked off with Ben Green’s first lecture in his series on Finite Field Models (and in particular, to problems simulating outstanding problems in additive combinatorics). What was quite novel about this talk was that the news about the Sunflower Conjecture was placed in the centre of his talk: it was a news breaking talk. Add to this Tao’s reformulation of the Croot-Lev-Pach principle, and it really felt like everything we were being told was hot off the press. The next talk was by Peter Cameron, and he spoke about some problems to do with synchronisation (for automata and permutation groups). I was reminded that we still not have an idea what is going on with acting on k-subsets for . Something perhaps worth thinking about when I have time. Then Kai-Uwa Schmidt spoke about his recent results on o-polynomials; which are the functions you get when you coordinatise a hyperoval in a finite Desarguesian projective plane. I remember seeing his papers on the arxiv some time ago, so it was nice to see it all placed in context: some very nice recent results there on a problem that hasn’t seen many advances for a while. There were two citations of SymOmega in his talk: one of them was a comment I made about hyperovals, the second was a comment from Tim Penttila.
In the afternoon, Peter Keevash set the scene for his series on designs. He gave his big result of yesteryear, and all of its many consequences: Wilson’s Conjecture and the Existence Conjecture. He has only just outlined the strategy behind the proof, so the best is yet to come. I then gave the first talk after afternoon tea: it was a tad rushed, but I managed to get to the end. After my talk was a summary of the EKR problem for finite polar spaces by Klaus Metsch. Klaus has produced many interesting results in this area of late, and often by applying the Hoffmann bound to linear combinations of adjacency matrices of an association scheme! He showed that good old finite geometry techniques pair up well with the algebraic combinatorial techniques, when both cannot do the job alone.
There might be more reporting tomorrow … if I have time.
Cai Heng Li, Gabriel Verret and myself are currently advertising for a two year postdoc to work on our ARC grant entitled `Symmetries of finite digraphs’. The deadline is the 19th of February. More details are available at
Over the last few years, Minion (I’m giving the link because if you try to search for it, you’ll be swamped by Despicable Me merchandise) has become one of my “go-to” tools, mostly because for certain specific types of searches it seems to perform just as well as, or even better than, a bespoke program. And of course, writing, debugging and optimising a bespoke program is enormously time-consuming, while writing a Minion model is usually very quick.
Most recently, I had an email from Brendan (McKay), who has found three planar cubic graphs of girth 5 that are hypohamiltonian – a graph is hypohamiltonian if it is not hamiltonian, but for every vertex , the graph is hamiltonian. Brendan’s graphs had 76 vertices, so not huge, but big enough.
This is the story of the shameful conjecture, which started with Dominic Welsh, was almost solved by Paul Seymour, and eventually resolved by my friend Fengming Dong from Nanyang in Singapore.
The conjecture concerns a graph parameter called the mean colour number defined as follows: If is an -vertex graph, then is the average number of colours used over all proper colourings of using a palette of n colours.
As this is a slightly strange parameter, an example is probably in order, and it seems only appropriate to use the Welsh graph (that is, the graph obtained by deleting one edge from ) for this purpose.
Using a palette of colours, there are colourings that use all four of the colours. There are colourings that use a fixed set of colours (the two vertices of degree two must be assigned the same colour), and there are ways of choosing colours of out , making a total of colourings using three colours. So the mean colour number of the Welsh graph is as the colourings are evenly divided between – and -colourings (there are no colourings with fewer than colours).
Using some straightforward identities, it can be shown that
where is the chromatic polynomial of .
The chromatic polynomial of the Welsh graph is so for this graph the expression has the value as expected.
It is obvious that the complete graph has the largest mean colour number, because every colouring requires colours, so .
At the other extreme is the empty graph on vertices, which has chromatic polynomial and thus
and as gets large the factor famously converges to from below.
But hang on, why did I say “the other extreme”? How do I know that the empty graph has the lowest mean colour number? Of course, it seems intuitively obvious that adding an edge to a graph can only increase the average number of colours required to colour it. Unfortunately, while it is intuitively obvious, it is not actually true that adding edges increases the mean colour number. Mike Mosca (yes, the quantum crypto guy from Waterloo) found an infinite family of counterexamples, of which the smallest has only 6 vertices.
So is it even true that is the extreme graph? Bartels and Welsh conjectured that this is indeed the case – namely that for any -vertex graph
For a graph theorist, it is a little embarrassing to define a parameter applicable to all graphs, with the complete graph trivially at one extreme, and then be unable to show that the empty graph is the other extreme. In fact, more than just embarrassing, perhaps even positively shameful.
Thus the shameful conjecture was christened.
Now Paul Seymour enters the ring. Normally if he turns his attention to some topic, even briefly, he quickly vacuums up and solves most of the known unsolved conjectures, generates some much harder and deeper conjectures, and then moves on. In this case though, he didn’t quite knock off the shameful conjecture. Instead, he proved that for any n-vertex graph ,
As , this value is just a little bit too low to prove the shameful conjecture.
The shameful conjecture hung on for another few years, but ultimately Fengming Dong (who has resolved quite a number of difficult chromatic and flow polynomial questions), used one of his typically intricate and ingenious proofs to show that the shameful conjecture is indeed true.
I don’t know if the shameful conjecture has stimulated any further research, or if the mean colour number has found any other uses, but I’ve always liked the story…
Written with StackEdit.
All the universities in Australia are having their “Open Day” events, which usually consists of a mix of a children’s carnival plus some information on courses and degrees for secondary school students. Just when you thought the marketing fraternity could not get lower, the geniuses at La Trobe University have introduced an instagrants campaign. The idea was that if you took a selfie in front of a designated research poster, then $150 would be given by the university to that research area. I wonder how long it will take the other universities to come up with this idea too!
We’ve just heard that John has been promoted, so let the celebrations begin!
Well done, John!
Last week I was at the 8th Slovenian Conference on Graph Theory. This was the latest in what is commonly known as the ‘Bled conference’ but this year was in Kranjska Gora. This meant that the conference excursion was to Lake Bled. It was a very enjoyable conference with lots of interesting talks and it was good to catch up with lots of people. I was one of the plenary speakers and my talk was entitled ‘Bounding the number of automorphisms of a graph’. This surveyed the recent work on the Weiss conjecture and its generalisation the PSV conjecture. It also discussed my recent work with Luke Morgan on the PSV conjecture for semiprimitive groups with a nilpotent regular normal subgroup. More details can be found on my slides.