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.
Automorphisms of a 76 million vertex graph
I’ve been meaning to write a post about practical graph automorphism finding for a while, and the last few days experience has finally prompted me to do so now.
The problem of finding the automorphism group of a graph — by this, I mean using software to actually determine the group as a permutation group — is pretty fundamental to a whole range of construction and counting problems. It is obviously very closely related to the graph isomorphism problem, which is to determine whether two graphs are isomorphic. This problem, known as GI, is a problem whose complexity is well known to be unknown (if you see what I mean!). Graph isomorphism is in NP, but it is not known to be either NP-complete or in P, so is a prime candidate for the problem of intermediate complexity that would show that P $\not=$ NP. Finding the automorphism group of a graph is at least as hard as graph isomorphism, because you could use an automorphism-finder to resolve whether G and H are isomorphic by computing the automorphism group of the disjoint union of G and H, and seeing whether any automorphisms swapped the components.
In practice, graph automorphism finding is relatively easy and the automorphism group can be calculated for large graphs, indeed enormous graphs! For more than three decades, the “go-to” software for finding automorphisms of graphs has been Brendan McKay’s program “nauty” which has been used by hundreds, even thousands, of researchers at various points. My thesis, nearly 30 years ago, used one of the early versions of nauty. There are other programs available of course, some of which outperform nauty on particular families of graphs, but none of which match the combination that nauty offers in terms of availability, long-term development and maintenance and overall performance.
Around 25 years ago, I noticed that certain graphs were proving particularly difficult for nauty to process, namely the bipartite point-line incidence graphs of non-desarguesian projective planes. At the time I was working with projective planes of order 9, which have 91 points and 91 lines, and so these were only 182 vertex graphs. I can’t remember the exact numbers, but it took about 0.5 seconds cpu time to process PG(2,9), about 10 seconds to process the Hall plane of order 9 and about 200 hours to find the automorphism group of the Hughes plane of order 9. Of course Brendan immediately put some effort into finding new invariants and other tweaks to make computing the automorphism groups of these projective planes graphs tractable, but they are still much more difficult than most graphs of the same size. (Other geometric graphs such as the incidence graphs of GQs are difficult, but not that difficult.)
A few years ago, Brendan and I were at a meeting in Bristol when we were approached by one of the other delegates who was keen to show us his results on computing automorphism groups of projective planes. He had devised a method of computing the search tree using a hybrid mixture of breadth-first and depth-first search — essentially a single run to the maximum depth of the tree yields an automorphism that can then later be effectively used to prune entire branches of the tree at a very early stage. The results were nothing short of spectacular, with huge projective planes now yielding in seconds rather than days. The researcher in question is called Adolfo Piperno, his technique is called Traces and Adolfo and Brendan have combined forces to refine both techniques and implement them robustly, with the final result being the imaginatively-named “nauty/Traces” package.
So how good is this in practice? For what size of graph can you realistically hope to determine the automorphism group? Pretty big is the answer to that question — in the last few days I’ve managed to use nauty/Traces to determine the automorphism group of a graph with just over 76 million vertices! This graph is a 10-regular graph obtained by taking a primitive representation of the group PSp(6,3) of degree 76422528, which has a non-self paired orbital of valency 5, which thus determines a digraph of out-valency 5. Dropping the directions on the arcs gives us a graph of valency 10. For various reasons, we wanted to know whether the full automorphism group of this graph is just the original PSp(6,3) or bigger.
Of course, it is impossible to store a 76 million x 76 million adjacency matrix, even if it is bit-packed, but fortunately Brendan has recently (in the last few years) added the ability to work with adjacency lists, thus basically using space proportional to the number of edges, rather than the square of the number of vertices. Just forming the file that defined the graph was a tedious process because GAP and Magma can’t do anything fast in groups of this degree, and there are many things that they simply cannot do at all (e.g. find the order of the group!). So I had to “hand-roll” lots of little bits of code that did basic things but in roundabout ways that didn’t use up too much memory and didn’t trigger anything that would never finish.
Once I had the file, the rest was simple. I actually just used the program dreadnaut which is a command-line user interface for nauty/Traces. The input file looked like this:
n=76422528 $=1 g 20385294, 22694895, 50999204, 58103886, 74686745 ; 14658604, 27594574, 45288953, 46264591, 69387673 ; (76422525 lines omitted) 3976598, 18300815, 27911643, 64737249, 74506343 . x
The first two lines set the number of vertices, then the base of the numbering (my vertices are numbered 1 to 76422528, rather than 0 to 76422527). The “g” puts it into graph-input mode, and the next 76422528 lines are the neighbours of each vertex — they are only specified in one direction but unless specified otherwise, nauty/Traces will automatically treat the graph as undirected. Finally, the “x” tells the program to compute the automorphism group.
This whole file — of size 3.6Gb — is then piped into the dreadnaut program with suitable flags to tell it to use Traces and the sparse representation. A little while later, after lots of output of the four permutations, I get the result
1 orbit; grpsize=9170703360; 4 gens; 9 nodes (6 peak);maxlev=2 cpu time = 1550.93 seconds
Unfortunately it wasn’t the result I wanted, because the group of the graph has doubled in size from the guaranteed PSp(6,3) and I was really hoping for this not to happen, because it would have yielded a primitive half-arc transitive graph of the lowest possible valency, whose existence is currently unresolved.
However, I am still hugely impressed that it is possible to find the automorphism group of a 76 million vertex non-trivial graph – in fact I’d really have to say that it’s spectacular!
By way of contrast, consider the NP-complete problem of finding the chromatic number of a graph. This problem is theoretically difficult, but it also seems to be practically difficult – already at 100-200 vertices, there are graphs whose chromatic number I simply cannot determine.
Written with StackEdit.
Dad, what does that sign mean?
This is what my 9-year old daughter asked when she saw these signs adorning a wall on campus when walking to her music class on Saturday. Without waiting for an answer from me, she immediately gave her opinion:
It doesn’t make any sense – and it’s not even proper English!
She’s right of course – what on earth does it mean? Pursue the impossible? Pursue impossible dreams? And why are the campus walls decorated with this ungrammatical imperative? And what are we meant to do if we acquiesce – start attempting to square the circle or find a 5-chromatic planar graph? In mathematics at least, pursuing the impossible is not such a great idea.
Then I remembered seeing some people installing various objects in different places about campus last week. At the time I had assumed that this was the output of an art project, but now I went for a closer look. The first thing I saw was a collection of parallel metal plates on the lawn with a sign saying “Take Photo Here”. So I did, and when I took the photo from the recommended place, the plates lined up and I got a picture of John Winthrop Hackett, who was UWA’s inaugural chancellor.
Because my first view of the structure (sculpture?) was at almost the same angle as the “correct” viewing angle, there wasn’t all that much difference between the views. The next one was more interesting though – again a set of parallel plates, and obviously a person, but who?
The photo is of Barry Marshall, UWA’s one and only Nobel Laureate (shared prize with Robin Warren) and he really does have one of the great stories of scientific persistence triumphing against the odds. While working as a young internist, he noticed high concentrations of the bacterium Helicobacter Pylori in many of the biopsies he performed on tissue from people with stomach ulcers and other stomach problems, and he developed the theory that stomach ulcers might actually be caused by the bacterium. At that time, stomach ulcers were universally regarded as arising from excessive stomach acid caused by stress and diet. The medical establishment greeted his theory with ignorance, indifference or condemnation. After all, who would pay any attention to this maverick whose nonsensical theories about bacteria living in the stomach causing ulcers were obviously so wildly misguided that they should be summarily rejected.
One of the important and most dramatic steps that he took to prove that he was right after all was to create a Helicobacter Pylori broth, and drink it himself, while documenting the survival of the bacteria in the stomach (deemed impossible) and the almost immediate onset of a number of stomach complaints. The ultimate consequence of his persistence, indeed intransigence, is that stomach ulcers have been transformed from a painful, often-chronic condition making life miserable for tens of millions of people to an easily-treatable condition just requiring a short course of antibiotics. Occasionally I see a car driving round Nedlands with the vanity plates H PYLORI on it.
By now, it’s dawning on me that this is not some final year project in Visual Arts, but is actually the unveiling of the University’s new branding – yes, our new “slogan” or “motto” or whatever you call it is actually “Pursue Impossible”. I didn’t attend the meeting at which this branding was unveiled and explained, so I had to fill in the gaps myself. The installations are all about how by looking at things in just the right way, the impossible becomes possible. To my mind, the sentiment is fine, but not immediately apparent from “Pursue Impossible”.
Also some of the installations don’t seem to really be conveying the right idea. In this one, the word POSSIBLE on our staff club wall becomes IMPOSSIBLE if you manoeuvre the letters IM (sitting on a plinth some distance away) into place. So by looking at it in the recommended way, the possible becomes impossible! Hurray!
So what do we all think of our new motto? Everyone that I’ve spoken to has reacted with either disbelief, bewilderment or derision, but I’m not sure which is winning at the moment. I don’t know if anybody (other than the marketing firm that pocketed the cash) likes it, but if they do, they haven’t told me.
Our previous but now-outdated motto was “Achieve International Excellence” which is pretty clunky but at least the intent is clear. Even earlier we had a much more succinct motto with which surely no-one can disagree – “Seek Wisdom” – and to which I think we should return, if we really think a motto is important. But actually, what is the point of a university motto/tagline at all? Do students choose universities based on the motto? Is the motto intended to convey to the public some deeply held core value? If so, should it really be chosen by some marketing consultant?
It seems endemic though, because almost everywhere has a motto – for example, both of my daughters’ schools have mottos, one of them is Semper Altius and the other Savoir C’est Pouvoir. (Obviously, a motto in another language automatically has more gravitas than one in English.) The good news though is that we’re not the worst – when I went to UNSW a few years ago, I was surprised to be continually urged to Never Stand Still, which is their motto. To me, it always brings to mind the image of someone standing giving a lecture while hopping frantically from foot to foot, as though desperate for a pee.
I do have to feel a bit sorry for the VC though. Shortly after unveiling the “Pursue Impossible” brand, he was forced by UWA staff and students to reluctantly return $4m (to the government) that had been given to UWA to set up a think-tank analysing problems in the developing world and making recommendations on which development projects give the best bang for the buck. The catch was that the proposed centre was to be associated with Bjorn Lomborg, a Danish political scientist who performs “Freakonomics” style analysis of environmental and developmental issues, often with counter-intuitive and/or controversial results.
But UWA staff spoke loud and clear – they absolutely do not want to be associated in any way with this maverick whose nonsensical theories are obviously so wildly misguided that they should be summarily rejected.
Aha, at last I’ve got it – the motto that we should have if they were subject to truth-in-advertising rules.
UWA – you just can’t make this stuff up!