Automorphism groups of hypergraphs

I am getting old and forgetful, but I don’t think I said anything here about this problem yet. If I did, apologies for the repetition – but there is something new to report!

In April, Laci Babai and I finally polished a paper which we started in 1990, and sent it off to a journal. Perhaps the headline theorem of the paper asserts:

Except for the alternating groups and finitely many others, every primitive permutation group is the full automorphism group of a uniform hypergraph.

A famous theorem of Frucht states that every (abstract) group is the full automorphism group of a graph. However, it is not true that every permutation group is the automorphism group of a graph (acting on the vertex set of the graph); for example, the only graphs preserved by a doubly transitive group are the complete and null graphs, whose full automorphism groups are the symmetric group. Our theorem describes a way of making good this lack. (A uniform hypergraph is like a graph, except that its “edges” have some fixed cardinality k which is not necessarily 2.)

A permutation group G of degree n is set-transtive if any two subsets of the domain of the same cardinality lie in the same orbit of G. Thus, if G is set-transitive, then any G-invariant hypergraph consists of all or none of the k-subsets, for all k, and its full automorphism group is the symmetric group. Thus, set-transitive groups other than symmetric groups cannot be automorphism groups of hypergraphs. These groups include the alternating groups and just four others. This problem itself has an interesting history. It was posed in the first edition of von Neumann and Morgenstern’s Theory of Games and Economic Behaviour, and in the second edition they report that it was solved by C. Chevalley. But as far as I know, Chevalley’s solution was never published, and the solution is usually credited to Beaumont and Petersen. The four groups are: AGL(1,5), degree 5, order 20; PGL(2,5), degree 6, order 120; PGL(2,8), degree 9, order 504; and PΓL(2,8), degree 9, order 1512.

Laci Babai and I were asked this question by Misha Klin at a graph theory conference in Japan in 1990, and succeeded in solving it. We showed, further, that the automorphism group of the hypergraph could be taken to be edge-transitive, even edge-regular, in general (that is, the stabiliser of an edge is the identity), and that the cardinality of the edges could be taken to be n3/4+o(1). I was in favour of publishing the result, but Laci held out for an improvement of the last fact to n1/2+o(1). This was eventually achieved (largely by his efforts), but by then the theorem had sunk down the pile.

One of the antecedents of this theorem was one I proved with Peter Neumann and Jan Saxl in 1984: apart from the alternating groups and finitely many others, a primitive permutation group has a regular orbit on the power set of its domain. My theorem with Laci shows that in general we can take such an orbit to be the edge set of the required hypergraphs. Now in 1997, Ákos Seress published a paper in which he found all the exceptions in the Cameron–Neumann–Saxl theorem. (There are exactly 43 exceptions, the largest degree being 32.) After his untimely recent death, Laci and I decided that our paper would be a suitable tribute to him.

The new thing to report is that Pablo Spiga has now found all the exceptions in the Babai–Cameron theorem. There are 15 of them, with degrees ranging between 5 and 10, and they include (as they must) the four exceptional set-transitive groups.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, mathematics and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s