3rd SYGN Workshop

Last week I was at the 3rd Symmetries of Graphs and Networks Worskhop and PhD Summer School in Discrete Mathematics at Rogla, Slovenia.  The SYGN meeting has been held every two years with the first being at Banff in 2008 and this was the second one held at Rogla. The summer school part continues on the tradition started last year.

Once again the Slovenians did a great job at organising it and it was a very enjoyable conference. I was invited to give a minicourse as part of the summer school on The Polycirculant Conjecture. I have touched on this previously. Boštjan Kuzman kindly took  latex notes of my lectures and these are available at the conference webpage together with the slides from the other courses and talks from the workshop. The other courses were on Graph enumeration by Stephan Wagner and Finite geometries by György Kiss.

Four talks that I found particularly interesting were:

  • Roman Nedela’s survey on regular maps. This gave a great overview of the area and I learned a lot about what the main problems in the area are.
  • Jozef Siran’s survey on the degree-diameter problem.
  • Joy Morris’s talk on the structure of circulant graphs.
  • Steve Wilson’s talk on Tales from the census. This is his census with   Primož Potočnik on 4-valent edge-transitive graphs.

Postdoc positions at UWA

We have two new postdoctoral positions in the “Centre for the Mathematics of Symmetry and Computation” here at UWA, funded by two Australian Research Council Discovery Project grants. Both are two-year positions and in the fields of finite permutation groups and combinatorics. One position is on a grant held by myself and the other is on a grant held by John Bamberg and Cai Heng Li.

The deadline for applications is 27th April (2012).

More details and instructions on how to apply can be found here (refs 3962 and 3963).

We look forward to lots of applications from SymOmega readers.

Symmetries of Discrete Objects

I am just back from Queenstown, New Zealand where I was attending the Symmetries of Discrete Objects conference.  The conference was well attended with many people from the graph symmetry, maps on surfaces and polytopes communities in attendance.  The conference also served as a Magma workshop with four two lecture mini-courses on aspects to do with Magma. The conference was very well organised by Marston Conder from the University of Auckland and it was announced at the end of the conference that his colleague Dimitri Leemans will organise a sequel in four years time in Nelson.

The conference also won the award for most spectacular view from a lecture room: looking out across Lake Wakatipu to the Remarkables mountain range.

Some talks that I found particularly interesting were:

  • Ian Wanless’s on autotopisms of Latin squares
  • Tomaz Pisanski’s on GI graphs ( a generalisation of generalised Petersen graphs)
  • Steve Wilson’s on Tricirculant edge-transitive tetravalent graphs
  • Tom Tucker and Wilfried Imrich’s talks on distinguishability of graphs
  • Gabriel Verret’s on his new census of cubic vertex-transitive graphs that I discussed in an earlier post 

I also discovered during Eamonn O’Brien’s Magma course on PC-presentations that Sylow’s famous paper included a forgotten 4th  theorem that essentially states that a p-group has a power-commutator presentation.

I spoke on my recent work on imprimitive rank three groups with Alice Devillers, Cai Heng Li, Geoffrey Pearce and Cheryl Praeger.

Connecting finite and infinite mathematics through symmetry

I am just back from going to the AMSI workshop on `Connecting finite and infinite mathematics through symmetry‘ held at the University of Wollongong. The workshop was essentially an Australian group theory conference and was a great opportunity to hear what people in Australia were working on in the area. Unlike the  annual combinatorics conference held in Australasia there is no regular gathering of the group theorists apart from at the annual meeting of the Australian Maths Society. It would definitely be good to have  more regular meetings of a group theoretic flavour in the country.

The workshop was a great success with very good talks covering a wide variety of group theory. The areas covered ranged from computational group theory to totally disconnected locally compact groups and from geometric group theory to the graph isomorphism problem, with lots in between.

I gave a  talk on my work on 3/2-transitive permutation groups. It mainly focussed on the work I have done in the finite case with various coauthors  but in keeping with the theme of the workshop also included a few thoughts on the infinite case.

Cubic vertex-transitive graphs

A graph is called vertex-transitive if for every pair of vertices there is an automorphism of the graph that maps the first to the second. I discussed such graphs and other symmetry classes of graphs in two earlier posts. (I see that I had promised a third in that series but that has yet to eventuate.)

A cubic graph is a graph for which every vertex has valency three, that is, every vertex has exactly three neighbours.  Cubic graphs have been extensively investigated with many graph properties first investigated in the cubic case. For example,  s-arc-transitive graphs were first investigated in the cubic case in the seminal work of William Tutte in two papers in 1947 and 1959.

An arc of a graph is an ordered pair of adjacent vertices and we say that a graph is called arc-transitive if the automorphism group of the graph acts transitively on the set of arcs. The most famous example is the Petersen graph. Arc-transitive graphs are also called symmetric graphs.  Ronald Foster began compiling a list of symmetric cubic graphs in 1932 and this is now known as the Foster census. Marston Conder and Peter Dobcsanyi  extended the census so that it was complete for graphs with at most 768 vertices and Marston has extended it further to include all graphs with at most 2048 vertices. The graphs are available on Marston’s website.

For vertex-transitive cubic graphs there is data collated by Gordon and Brendan McKay that is complete for all graphs with up to 94 vertices as well as all graphs with n vertices for many values of n at most 258. Recently, Primoz Potocnik, Pablo Spiga and Gabriel Verret have comprehensively smashed this upper bound by compiling a list of all vertex-transitive cubic graphs with at most 1280 vertices. This continues the excellent work in graph symmetry that they have been doing in recent years. They have set up a webpage containing the data and a preprint is on the arxiv explaining their methods. I am sure it will be a valuable resource for investigating graphs and testing conjectures. They have already checked that apart from the four known exceptions they each have a Hamiltonian cycle.

As part of their work they have also compiled a list of all arc-transitive graphs of valency 4 on at most 640 vertices. That is also available on their webpage. Primoz is also undertaking a project with Steve Wilson aiming to list all edge-transitive valency 4 graphs on up to 512 vertices. The data so far is available here.


I am currently in Beijing visiting Jing Xu at Capital Normal University. This is the second time I have been to China so I already knew a little of what to expect. Beijing  has the added advantage of being in the same time zone as Perth so despite the 13-14 hour journey to get here, there were no problems with jet lag.

The food is very tasty even if you don’t always know what you are eating. My many years  eating chicken teriyaki from the Japanese Gourmet Food to Go place on Hampden Road means that my chopsticks skills are passable. Ordering in restaurants when the only Chinese words I know are hello, thankyou, rice and beer has also been an interesting experience. Thankfully many restaurants have pictures on the menu. There was one memorable episode when I was eating with a group of people, all with about as much knowledge of the language as me. As part of our meal we ordered two plates of dumplings. When they hadn’t appeared a good 15 minutes after the rest of the food, we asked about them (not sure how though), only to then have eight plates of dumplings appear. Five minutes later another two plates (probably the original two we had asked for) appeared.

Last week while I was here, I attended the Workshop on Group Actions on Combinatorial Structures that was very well organised by Shaofei Du and his colleagues at Capital Normal. I think the workshop was a great success with a wide variety of talks and generous hospitality from the organisers. Some talks that I found particularly interesting were:

-Klavdija Kutnar’s on the classification of cubic symmetric polycirculants.
-Dragan Marusic’s on two open problems in vertex-transitive graphs. One was finding a CFSG-free proof of the nonexistence of a primitive group of degree 2p that is not 2-transitive. The other was on finding vertex-transitive snarks. A snark is a connected bridgeless cubic graph that is not 3-edge colourable and the Petersen graph is the only known vertex-transitive one.
-Steve Wilson’s on small rotary maniplexes. A maniplex is a generalisation of a map (an embedding of a graph onto a 2-dimensional manifold) to higher dimensions.
-Robert Jajcay’s on the role of groups and symmetry in the cage and degree/diameter problems.
-Shenglin Zhou’s comprehensive survey on automorphism groups of block designs.

I spoke about my work with John on groups acting regularly on generalised quadrangles that I have discussed here before but with an emphasis on how our examples answered a question on normal Cayley graphs.

Journal of Group Theory

Good news. The dispute at the Journal of Group Theory noted earlier has been resolved. Chris Parker sent the following email to the group-pub-forum today.

The complete editorial board of the Journal of Group Theory have
come to a negotiated settlement with the publishers Walter de
Gruyter. John Wilson will continue to act as the Editor-in-Chief.
Jim Howie, Linus Kramer and Chris Parker will act as Managing
Editors, supporting John. The key points of the agreement are:

Joint ownership of the journal title and distribution list.
Free online access to all articles 36 months after publication.
Agreement to donate electronic access to certain requested 
journals to Oberwolfach.
A pledge to help third world countries to access the journal.

The entire editorial board are now ready to receive submissions 
of high quality articles with main theme being  group theory 
and its applications.

The editorial board is as follows:

Miklos Abert
Alexandre V. Borovik
Nigel Boston
Martin R. Bridson
Michel Broue
Francesco de Giovanni
Robert Guralnick
James Howie
Andrei Jaikin Zapirain
William M. Kantor
Evgenii I. Khukhro
Dessislava H. Kochloukova
Linus Kramer
Gunter Malle
Alexandre Yu. Olshanskii
Christopher W. Parker
Derek J. S. Robinson
George Willis
John S. Wilson

From, Linus Kramer, James Howie, Chris Parker and John Wilson.

We can now go back to submitting articles there.


Last week and this week I have been at the University of Southampton visiting Tim Burness to work on our big project concerning derangements. Despite it being summer here, the weather has been  more like a Perth winter. I am staying in a self-catered hall of residence so the cooked breakfasts have come to an end and it is back to cornflakes.

A derangement is a permutation that moves all the points of the set which it acts on.  I have only recently been converted to the term derangement, have previously preferred the term fixed point free element. Peter Cameron has had a bit to say about derangements in several posts on his blog.

By the Orbit-Counting Lemma, the average number of fixed points of an element of a transitive permutation group is 1. Since the identity permutation fixes all the elements of the set,  a transitive permutation group on a set of size at least two must therefore contain a derangement.   This leads to the natural questions that have attracted a lot of attention:

  • how many derangements are there?
  • what properties do the derangements have?

The project with Tim focuses on the second.

Fein, Kantor and Schacher proved that every transitive permutation group contains a derangement of prime power order. The result was motivated by an application to number theory as the existence of a derangement of prime power order is equivalent to the relative Brauer group of any nontrivial field extension of global fields being infinite. Whereas the existence of a derangement is an elementary observation, the proof of the existence of one of prime power order relies heavily on the Classification of Finite Simple Groups. The proof though does not give information about which primes or which powers.

In fact, not every transitive permutation group contains a derangement of prime order. My favourite example is the Mathieu group M_{11} in its 3-transitive action on 12 points.  Note that if a group G acts transitively on a set with the stabiliser of some point being the subgroup H, then an element g fixes a point if and only if it is conjugate to an element of H.   Since M_{11}  contains a unique conjugacy class of elements of order 2 and a unique class of elements of order 3, and 6  divides the order of the stabiliser of a point (PSL(2,11)), it follows that all elements of order 2 and 3 fix a point.

Continue reading “Derangements”

Up ↑