Graph Theory at Kranjska Gora

I’ve just returned to Perth after giving one of the plenary talks at the “10th Slovenian Conference on Graph Theory” held in small ski-resort town of Kranjska Gora. I had never been to Slovenia before and hadn’t realised how spectacularly beautiful it is. Lush green forests, steep mountains and azure alpine lakes complemented with a scattering of castles, churches and other historical buildings combine to make a scenic wonderland.

It is of course a long way to go for a conference, but because travel has been so restricted for the last few years, and because I was one of the plenary speakers, I felt that it was an opportunity (for visibility, contacts, impact etc) that I would be foolish to miss. As it turns out, I’m very glad that I went, because I did indeed meet and talk to many people, from decades-old acquaintances to new PhD students.

I went a few days early to give me time to overcome jet lag and was fortunate enough to be able to join the conference organiser Primož Potočnik and a few others in the town of Bled, staying in the villa formerly owned by Josip Premelj, the first rector of the University of Ljubljana. Bled itself is renowned for its picture-postcard scenery, in particular Lake Bled with its island church and overlooking castle. Bled is also famous for its kremšnita (cream cake) whose deliciousness I can personally verify, and for the naturopath Arnold Rikli. He believed that exercising naked in the sunshine and bathing in cold water surrounded by the glories of nature was good for both body and soul, an opinion not necessarily shared by the citizens of Bled in the 1860s.

Lake Bled, Slovenia in June 2023

The conference itself was held in Kranjska Gora which is a small town about 30 minutes from Bled. The town lies in a valley surrounded by ski-slopes and appears to exist entirely to service skiers in the winter and adventure tourists (mountain bikers, climbers, hikers and kayakers) in the summer. As a result, it has hotel, dining and other facilities out of proportion to its size and is probably extra keen on attracting summer visitors.

With 340 registered participants (apparently many more than anticipated), the conference had to spread over two large hotels about 100m apart from each other and had, at times, 7 parallel sessions. This made for many difficult decisions particularly as it not really practical to switch hotels between consecutive talks. On the plus side, there was almost always at least one of the parallel sessions with a talk that interested me.

UWA was well represented in various ways among the plenary speakers. In addition to myself, there was David Wood, who did his undergraduate degree at UWA (in fact, I taught him Algorithms sometime last century) and Anders Yeo who is the son of former UWA academic Geoff Yeo who still lives in Perth (I think Anders said that to me in passing).

I went to far too many talks to comment on all of them, so I’ll just talk about one that particularly interested me. Gary Greaves from NTU (Singapore) gave a very nice talk on graphs with three distinct eigenvalues. Strongly regular graphs have this property but as these are already very heavily studied, the talk was really about non-regular graphs with three distinct eigenvalues. These can be stratified by the dimension of the minimal coherent algebra containing the adjacency matrix of the graph, and when this dimension is low it is possible to find complete characterisations involving other combinatorial objects such as symmetric designs, quasi-symmetric designs etc. Gary also mentioned an intriguing conjecture (or question) due to my old friend Dom de Caen.

Question: Is it true that a connected graph with three distinct eigenvalues has at most three distinct vertex degrees?

Pushing Limits At Dagstuhl

So my first international trip since Covid happened has been to a CS/Maths Research Centre “Schloss Dagstuhl” located in a fairly rural area in Germany.

Schloss Dagstuhl, Wadern, Germany

Similar to various other research centres around the world, the idea is to gather together a bunch of academics for a week in a location with few external distractions, have a few talks and tutorials, and plenty of time for working groups. The Australian version of this model is the MATRIX Research Institute in Creswick, Victoria, though as this uses former student accommodation blocks, it is not quite as comfortable.

The topic of this seminar was “Pushing the Limits on Computational Combinatorial Constructions” which gathered together a group of people working on combinatorial computing, in particular combinatorial search, generation of combinatorial catalogues and the existing, new and improved tools needed for these talks. So I felt that I really had to go, even though my body is telling me that I can no longer travel long distances for short times.

Despite the jet-lag it was great to catch up with old friends and to meet some of the younger people doing very interesting work. One of the more prominent themes that emerged during the workshop was the use of SAT solvers to solve combinatorial problems. Many combinatorial questions about the existence of combinatorial structures or substructures be modelled as a SAT instance. Often the number of clauses blows out because things such as calculating intersection sizes or testing connectivity often requires a seemingly enormous number of auxiliary variables. However SAT is very heavily studied and modern SAT solvers can cope with very large instances (at least, often enough to make it worthwhile trying). We heard about SAT being used to improve bounds on the smallest known Kochen-Specker graphs, about SAT being used (in vain) to find counterexamples to Rota’s Basis Conjecture at rank 4, and about SAT being used to verify (significant parts of) the proof of the non-existence of the projective plane of order 10.

I talked a bit about the nature of computational results, talking about the computer proof of the 4-Colour Theorem, the computer proof of the non-existence of the projective plane of order 10 and why these were (and in some circles still are) viewed with suspicion. I also described Blackburn, Crapo and Higgs construction of the catalogue of matroids on up to 8 elements in 1969. For many years, the list of “known excluded minors” for quaternary matroids omitted one matroid that was just sitting in the catalogue, and perhaps knowing this would have helped resolve the question sooner. I assume that before computers were commonplace, it was simply too hard to access the catalogue.

We had a nice excursion to a local beauty spot where the Saar River does a tight loop in steep forested terrain, with various hiking trails. Ian Wanless and I ended up doing a steep hike together with some fairly gruelling uphill stages (at least for me). David Pike saw us setting off and got a nice photo of us.

Saar Loop, Mettlach, Germany

Our last couple of days were enlivened by the planned train strike on Friday disrupting everyone’s travel plans. After wasting a lot of time trying to find alternatives, I was rescued by Adolfo “Traces” Piperno, who was driving to Frankfurt Airport and took me and one other to catch our early evening flights, despite his own flight being several hours later. The trip was mostly smooth, although as we got very close to the airport, the GPS in our phones seemed to get confused by the sheer number of roads and lanes all converging and crossing over and under each other, so at various stages my GPS was instructing us to “Turn right now” at exactly the same time as Adolfo’s was saying “Gira a sinistra”.

But since this was the culmination of a week of computational combinatorics, a little back-tracking seemed entirely appropriate and we eventually found our way.

nauty for your iPhone

How often have you been out somewhere, maybe at a restaurant or pub, and suddenly needed to generate some graphs, or determine the canonical labelling of a graph that has come up in conversation, only to be foiled because you don’t have your laptop with you.

Not often, you might say.

But just in case, here are some instructions for installing geng and nauty on your iPhone, so that you can be fully prepared in case the need suddenly arises.

It’s actually pretty easy to do. Start by installing the app iSH from the App Store – this provides a lightweight version of Linux (Alpine Linux) that you can interact with through the normal Unix command-line interface. (This is not just a terminal app making a connection to a remote server – it is actually Linux running on your iDevice.)

Conveniently, it supplies some extra keys on its virtual keyboard, including “tab” (for tab-completion), “ctrl” (for ctrl-C, etc) “esc” (for toggling modes in vi) and a key that is used like a 4-way rocker to replace the arrow keys (just drag your finger right, left, up or down to get the associated key). You may also need to turn on an option called “Disable Screen Dimming” so that the iPhone’s battery saving doesn’t interrupt long running processes like compilation.

Special keys on the iSH terminal

That said, using vi like this is a bit painful, so I used the Mac KeyPad App which you run on the Mac, connect to your iOS device, and then redirects any keystrokes from your Mac keyboard to the iOS device. So editing is now easy.

Next step is to install gcc and associated libraries in order to compile anything. This is easy to do using the iSH/Alpine package manager APK.

$ apk build-base

(Here, I am using the convention that the command-line interface uses a $-sign as a prompt awaiting user input. The actual prompt on your phone/tablet will vary from this, using some combination of the device name and current working directory – mine is “Gordons-iPhone:~#”. In any case, you don’t type the $ but just the command after it.)

Then wait for a while while it connects to the right repositories and downloads and installs the various things. For some reason, I kept getting a spurious message about “Temporary error”, but it seemed to install fine anyway.

Next download the nauty source code using wget direct from Brendan’s webpage, uncompress and extract the files from the tar archive and change into the directory that has just been created. Then run the configure tool to create a makefile.

$ wget http://users.cecs.anu.edu.au/~bdm/nauty/nauty27r3.tar.gz 
$ tar xzf nauty27r3.tar.gz
$ cd nauty27r3
$ ./configure

Now at the moment (i.e., with nauty27r3) this creates a makefile that creates a defective version of geng that crashes, due to the compiler dealing with a particular option incorrectly. So the next step is to edit the makefile manually, and remove the “-march=native” from line 6 of the makefile.

CFLAGS = -O4 -march=native

(Future versions of nauty will work around this problem.)

Now it’s time to go to lunch. Before you go, just start the compilation process.

$ make all

This is very time-consuming, taking about 45 minutes on my iPhone (12 mini), so have a reasonably long lunch. When you get back, it should be done, and now have a fully-functioning version of nauty and geng on an iPhone. (Of course, this works for iPad also.)

So now, I can generate the graphs anywhere and any time!

As you can see from the image, it takes about 4 seconds to generate, but not print out, the graphs on 9 vertices.

Screenshots of nauty in action on iSH

How does this compare to my desktop iMac?

The same task takes 0.08s – about 50 times faster. So “nauty on iOS” is not really going to be very useful on a day-to-day basis, but sometimes it’s fun to do something just because you can.

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.

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).

 

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).

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 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.