# automorphisms of graphs and finite permutation groups

I am interested in automorphisms of graphs and in using tools from permutation groups (especially such as in Wielandt's text on finite permutation groups, which I have been studying). What are some particular open problems, research directions or recent work that could be worthwhile to pursue or extend?

Chris Godsil mentions on his website that "If you want to actually work with automorphism groups of graphs, Wielandt offers a wealth of useful tools which you can either learn here, or be forced to reinvent." I would essentially like to obtain an elaboration of this sentence. Any references to papers would be appreciated.

• This should be community wiki. – HJRW Mar 26 '13 at 10:05

This question is probably going to turn into a community-wiki style list of favourite open problems concerning permutation groups and graphs. So, for what it's worth, here are two of mine:

The Weiss Conjecture: Let $G$ act vertex-transitively on some graph $\mathcal{G}$ of valency $k$. Let $v$ be a vertex of $\mathcal{G}$ and assume that $G_v$ acts primitively on its neighbours. Then $|G_v| \leq f(k)$ where $f:\mathbb{N}\to \mathbb{N}$ is some function depending only on $k$.

There is a wealth of work on this conjecture by many people. I would particular recommend this paper by Potocnik, Spiga and Verret, where the conjecture is discussed at length and some more general conjectures are also proposed. I'd also recommend this paper by Praeger, Pyber, Spiga and Szabo, in which substantial progress towards a proof of the conjecture is made.

All of the papers dealing with this conjecture make heavy use of permutation group techniques; recent papers also tend to make use of results coming out of the classification of finite simple groups.

The classification of regular maps: A map is a `nice' embeding of a graph on a surface, in a way that generalizes the notion of a planar graph. The map is regular if (to choose one of several slightly different definitions) it admits an automorphism group that acts as homeomorphisms on the surface, and is transitive on vertex-edge incident pairs.

The subject is very old (cf. the platonic solids), but the modern concern with these things began with Brahana and Coxeter and, then a few years later, with this beautiful paper by Jones and Singerman. There is now a wealth of literature aimed at classifying regular maps subject to constraints on, for instance, the underlying surface, the underlying graph, or the automorphism group. Prominent authors include Conder, Siran, Jones, Nedela, Breda d'Azevedo, Tucker, Archdeacon etc etc. Permutation group techniques are commonly used, as well as ideas from topology, group generation, Riemann surfaces etc.

The notion of a map is closely related to the important notion of a dessin d'enfant which was the subject of a famous paper by Grothendieck. There is a whole other school of work looking at maps from this perspective, however (to my knowledge) the emphasis in this school is not on the permutation group approach, and so may not be of so much interest to you.

• regarding dessin d'enfant, I liked this book by S.Lando and A.Zvonkin: springer.com/mathematics/geometry/book/978-3-540-00203-1 Other than that, I can't help noticing that our answers have virtually empty intersection. :–) – Dima Pasechnik Mar 26 '13 at 11:49
• @Nick Gill: that was informative. Thanks for the links. – user32526 Mar 27 '13 at 2:03

IMHO, the main message in Wielandt (you might want to supplement it by a more recent book, such as Peter Cameron's "Permutation groups") is that one can consider the adjacency matrix $A$ of your graph $\Gamma$ as an element of the centralizer ring {$X\in M_{|V\Gamma|}\mid Xg=gX$ for any $g\in G$} of the permutation representation of a subgroup $G$ of the automorphism group of $\Gamma$.

This idea has been used a lot since Wielandt's work, e.g. D.Higman and others axiomatised this point of view (one can throw away the group and look at rings which "look like" centralizer rings of permutation groups), resulting in emergence of a whole branch of algebraic combinatorics, the theory of coherent configurations and association schemes. It also had quite an influence on the theory of graph spectra.

The papers on this and other related ideas are too numerous. I'll mention (with apologies to the authors of relevant books I fail to mention) few books: apart from Peter Cameron's "Permutation groups", there are indeed books by Chris Godsil, the book "Algebraic combinatorics I. Association schemes" by E.Bannai and T.Ito, the book "Distance-regular graphs" by A.Brouwer, A.Cohen, and A.Neumaier.

A more graph-theoretic/CS point of view comes from work of L.Babai, see e.g. this survey.

The relations to spectra of graphs can be found in a recent book by A.Brouwer and W.Haemers.

• I agree entirely with what Dima has written, but in the text quoted above I was actually thinking of the many useful details about permutation groups that appear in the first few chapters of Wielandt's book and which I have not seen elsewhere. – Chris Godsil Mar 26 '13 at 11:21
• @Chris Godsil: I was wondering if you could please elaborate further. – user32526 Mar 27 '13 at 1:13

The most fundamental result is that associated to a dessin d'enfant (map or hypermap) on a surface X there is an associated complex structure on X that makes X a Riemann surface and hence an algebraic curve. This was first proved in my paper "Automorphisms of maps, permutation groups and Riemann surfaces", Bull.London Math.Soc. 8 (1976). Much more detail appeared in G.A.Jones and D.Singerman, "Theory of maps on orientable surfaces" Proc. London Math.Soc. 37(1978) 273-397. Later in Esquisse d'un programme (1984) Grothendieck had this result and observed much, much more, namely Belyi's theorem implies that the an algebraic curve defined associated with a dessin is defined over the field of algebraic numbers. Also, the work of Jones,Singerman was implicit in the work of J.Malgoire and C.Voisin (Grothendieck students?) in 1977. For regular maps all this goes back to the work of Klein. See also Chapter 8 of Coxeter and Moser.