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

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.

Synchronising diagonal type groups exist

Recently, Michael Giudici, Jesse Lansdown, Gordon Royle and I have constructed a couple of examples of synchronising groups that are radically different from the known examples. You can find the details in our preprint here.

What is a synchronising group?

The definition came about from the study of synchronising words for finite-state automata. Motivated by the Černý Conjecture on the length of reset words in synchronising automata, Arnold and Steinberg, and independently Araújo, introduced the notion of a synchronising group. We say that a permutation group G is synchronising if for any non-bijective transformation f, the transformation semigroup \langle G, f\rangle is synchronising; that is, it contains a constant map (aka. reset word). It was observed in Peter Neumann’s seminal article in 2009 that a synchronising permutation group is primitive. Moreover, the possible O’Nan-Scott types for a synchronising group are heavily restricted. We have just three types: (i) Affine, (ii) Almost Simple, (iii) Diagonal. There are many examples in the first two cases known, but it wasn’t known until now whether the third case was nonempty.

What was known about synchronising diagonal groups?

Due to the fine work of many people, the shape of a diagonal type group had been whittled down. The diagonal group D(T,n) is defined as follows. Firstly, T is a nonabelian simple group, and n is a positive integer at least 2. The domain for our group action will be the direct product T^{n-1}. The group T^n acts diagonally on this set in the following action:

(t_2,\ldots,t_n)^{(x_1,\ldots,x_n)}=(x_1^{-1}t_2x_2,\ldots, x_1^{-1}t_nx_n)

We can include inner automorphisms acting identically on each coordinate in D(T,n), we can have permutations of the coordinates, and also a funny involution (which I won’t describe here). These generate the largest diagonal type primitive group on this domain, and a diagonal primitive group is a subgroup of D(T,n) containing the socle T^n.

Bray, Cai, Cameron, Spiga, Zhang (arXiv, 2018) showed that synchronising diagonal type groups have n=2. Moreover, they showed that “synchronising” and “separating” are equivalent for diagonal type primitive groups. In particular, if T as an exact factorisation, then T\times T is non-synchronising. For more, see Peter Cameron’s excellent post on this major breakthrough.

The examples

Take T=PSL(2,q), where q\in\{13,17\}. These are the smallest values for which it was not known if the group T\times T acting in diagonal action was synchronising or not. (For q\equiv 0,2,4\pmod{4}, and q\in\{5,29\}, we have an exact factorisation of PSL(2,q). The case q=9 was shown to give a non-synchronising example). Then we show that G=T\times T acting on T in diagonal action is synchronising. To show this, we needed to show that the action is separating and apply Bray, Cai, Cameron, Spiga, Zhang’s result that synchronisation and separation are equivalent for diagonal actions. To show that these groups are separating required us to show that every G-invariant undirected graph on T has \alpha\omega\ne |T| where \alpha and \omega are the maximum sizes of a coclique and clique (respectively) of the graph. This in turn needed the theory of association schemes, and in particular, design-orthogonality, to reduce the problem to the analysis of just a small number of graphs.

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.

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

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:

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.

Another postdoc position

Gordon, Michael, and I are currently advertising a 2.5 year postdoc position to work on the ARC Discovery Project “The synchronisation hierarchy of permutation groups” in the CMSC at The University of Western Australia. Applicants should have a PhD in mathematics and a background in permutation groups and/or finite geometry.

The deadline is the 28th of February, 2020.

Details of how to apply can be found at

Postdoc Position at UWA

I am currently advertising  an 18 month postdoc position to work on the ARC Discovery Project “Graph symmetry and simple groups” in the CMSC at The University of Western Australia. Applicants should have a background in permutation groups, simple groups or graph symmetry. The deadline is the 30th of January.

Details of how to apply can be found at

People interested in other postdoc positions in Perth should keep their eyes posted as there should be another advertisement appearing soon.

PhD scholarships

Applications are now open for scholarships for international PhD students at UWA to commence in the first half of 2019.  Myself and other members of the CMSC are interested in taking on new PhD students so if you are interested then please contact one of us about applying.

The deadline is the 31st of August 2018. Please see here for details on how to apply.

Please note that applications are ranked at our faculty level and in particular there are no scholarships specifically devoted to mathematics students.  In particular the process is highly competitive.