Help Wanted (PhD Scholarship)

We are advertising a PhD scholarship on the “synchronisation hierarchy of permutation groups” as part of the ARC Discovery Grant that we have for this.

https://www.scholarships.uwa.edu.au/search/?sc_view=1&id=10764

An Honours or Masters degree in Pure Maths is required, and the more experience in groups, permutation groups and geometry, the better.

Closing date is 28 Feb 2021.

Cheryl Praeger – Companion of the Order of Australia

Each Australia Day (26th January, for the time being), part of the festivities is the awarding of Honours to various people who have made exceptional contributions to the Australian community.

Often these honours go to former politicians or sportspeople whose political or sporting excellence, at least in my opinion, has primarily benefited themselves.

Sometimes though, the committee gets it right, and awards Honours to people who, in addition to excellence in their chosen profession, have used their position and their skills to benefit the wider community.

One such case is Cheryl Praeger, my PhD co-supervisor. Of course, she has outstanding personal accomplishments such as publishing hundreds of research papers, making history as the second Australian female professor of mathematics and being the recipient of numerous awards and accolades. But it is for her advocacy of the study of mathematics at all levels and her tireless efforts to enable and encourage women in particular to study mathematics that warrants this award.

The Companion of the Order of Australia is the highest Honour in the Australian system, and Cheryl is one of only four recipients this year.

For more details, see the ABC News announcement

https://www.abc.net.au/news/2021-01-26/professor-cheryl-praeger-receives-companion-order-of-australia/13089958

Gavin Brown Prize 2020

The Gavin Brown Prize is a “best paper” prize awarded annually by the Australian Mathematical Society, for work in any field of mathematics published no more than 10 years before the award.

To our great surprise but obviously immense delight, our 2010 paper “Every flock generalized quadrangle has a hemisystem” was awarded the 2020 prize.

The details of the prize can be found on the Australian Mathematical Society page, but in addition, UWA wrote a short news article about it, and the Vice-Chancellor even tweeted his congratulations.

This was the first paper that arose from our first joint ARC Discovery grant back in 2009, just after I had moved from the CS department to the Maths department at UWA, and started working with John and Michael.

I won’t discuss the actual details of the mathematics too much here, but just enough to describe what the problem is (was). A finite generalized quadrangle (GQ) is a particular type of finite point-line geometry that has no triangles, and flock generalized quadrangles are a large family of GQs. A hemisystem H is a subset of the lines of the GQ that contains exactly half of the lines on each point; from this it is essentially obvious that H must contain exactly half of the lines.

Hemisystems give rise to other interesting combinatorial and geometric objects, and so over several decades various researchers had tackled the question of when a GQ contains a hemisystem. At the time we started the work, the only recent progress that had been made was the discovery of an infinite family of hemisystems by Cossidente and Penttila in 2005.

Our paper answered the question in almost the strongest possible fashion – a construction for hemisystems in the very large family of flock GQs. The construction was elegant, the family of GQs to which it applied was large and it constructed exponentially many hemisystems. As it had previously been conjectured that hemisystems were very scarce, this was all totally unexpected.

In many areas of finite geometry, the usual case is that new interesting geometric configurations are found by intricate constructions that work in particular small families of geometries. In our ARC Discovery grant application we had “promised” to find some new small hemisystems, or possibly an infinite family for a particular class of GQs. As smashed through this goal in our first year, we were super happy at the time, and wrote a few SymOmega posts about it, such as the following one from John:

https://symomega.wordpress.com/2009/12/15/hemisystems-of-flock-generalised-quadrangles/

But to have this recognised by our colleagues and to be placed in the prestigious company of the former (and future) winners of the Gavin Brown Prize is something we could never have anticipated, but greatly appreciate.

Conferences

Long time since I (or any of us) last posted, but it would be good to get back into it again.

The winter months, especially June and July, are usually cold and rainy in Perth and this year is no exception.  So, like migratory birds heading for the sun, most of us head to the northern hemisphere for their summer conference season.

So I’m currently writing this from a student cafe at the University of Lisbon where a conference+workshop to celebrate Peter Cameron’s birthday is on its final day. But more of this particular conference later.

Continue reading “Conferences”

Baby Boom Continues

Congratulations to my postdoc Irene Pivotto and husband Robin Christian on the birth of their first child, Martin, born last week at St John of God hospital in Subiaco (which is where my daughters were both born).

 

babymartin
Irene, Robin and Martin

This is actually the second CMSC baby in a year, as Alice Devillers and Sam Norton had baby Emilia late last year – at the time I wasn’t keeping up with SymOmega at all due to pressure of work, so missed announcing it.

Better late then never though, so congratulations to both sets of parents!

Schloss Dagstuhl

It’s been a long time since posts, mainly due to the fact that logistical issues caused all my year’s teaching to be compressed into first semester (that’s late-Feb to early-June for any readers not used to Southern Hemisphere habits). It was pretty hard, especially as one of my units is a 550-student first-year Engineering Maths that I had not taken before.

But after many weeks of weekends, evenings or nights spent desperately trying to finish lecture notes, tutorials and solutions for the next day’s lectures, workshops and tutes, the semester eventually ended.

So rather than stay home to attend to the vast number of overdue non-teaching tasks (admin, refereeing, bureaucracy) that I’d had to resolutely ignore during the semsester, instead I flew straight to Germany for a week-long meeting on Graph Polynomials at Schloss Dagstuhl (in Saarland, southern Germany).

Continue reading “Schloss Dagstuhl”

Minion and hamiltonicity

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 G is hypohamiltonian if it is not hamiltonian, but for every vertex v, the graph G-v is hamiltonian. Brendan’s graphs had 76 vertices, so not huge, but big enough.

Continue reading “Minion and hamiltonicity”

The shameful conjecture

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 G is an n-vertex graph, then \mu(G) is the average number of colours used over all proper colourings of G 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 K_4 \backslash e obtained by deleting one edge from K_4) for this purpose.

Using a palette of 4 colours, there are 4! = 24 colourings that use all four of the colours. There are 3! = 6 colourings that use a fixed set of 3 colours (the two vertices of degree two must be assigned the same colour), and there are 4 ways of choosing 3 colours of out 4, making a total of 24 colourings using three colours. So the mean colour number of the Welsh graph is 7/2 as the 48 colourings are evenly divided between 3– and 4-colourings (there are no colourings with fewer than 3 colours).

Using some straightforward identities, it can be shown that

\displaystyle \mu(G) = n \times \left( 1 - \frac{P_G(n-1)}{P_G(n)} \right)

where P_G(x) is the chromatic polynomial of G.

The chromatic polynomial of the Welsh graph is x(x-1)(x-2)^2 so for this graph the expression has the value 4 \times (1 - 6/48) = 7/2 as expected.

It is obvious that the complete graph K_n has the largest mean colour number, because every colouring requires n colours, so \mu(K_n) = n.

At the other extreme is the empty graph on n vertices, which has chromatic polynomial x^n and thus

\displaystyle \mu(E_n)= n \times (1-(n-1)^n/n^n)

and as n gets large the factor (n-1)^n/n^n famously converges to 1/e from below.

But hang on, why did I say “the other extreme”? How do I know that the empty graph E_n 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 E_n is the extreme graph? Bartels and Welsh conjectured that this is indeed the case – namely that for any n-vertex graph G

\displaystyle \frac{P_G(n)}{P_G(n-1)} \geq \frac{n^n}{(n-1)^n} > e

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 G,

\displaystyle \frac{P_G(n)}{P_G(n-1)} \geq \frac{685}{252} \approx 2.7182539 \ldots

As e \approx 2.7182818 \ldots, 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.

Spectacular graph automorphisms

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.