Primitive switching classes

Last year I wrote here about switching classes of graphs for which the switching class has a primitive automorphism group. (I repeat the definitions briefly below.) I conjectured that, except for the trivial switching classes of the complete and null graphs and finitely many others, such a class must contain a graph with trivial automorphism group. This is an example of the point of view of Laci Babai: from the Classification of Finite Simple Groups we learn that conditions which seem to imply a great deal of symmetry (such as primitive automorphism group) actually severely restrict the amount of symmetry.

The operation of Seidel switching a graph with respect to a set S of vertices involves replacing edges between S and its complement with non-edges, and non-edges with edges, leaving edges and non-edges inside and outside S unchanged. This is an equivalence relation on the class of graphs on a given vertex set, whose classes are called switching classes. An automorphism of a switching class is a permutation which permutes among themselves the graphs in the class. An equivalent combinatorial concept is a two-graph, a collection of 3-element subsets of the vertex set with the property that any 4-element subset contains an even number of members of the collection. I talked about two-graphs at the Villanova conference, and you can find the slides here.

Soon after posting that, I was able to prove the conjecture. Now Pablo Spiga and I have worked out the finite list of exceptions. Up to complementation, there is just one such switching class on 5, 6, 9, 10, 14 and 16 vertices, and no others. The automorphism groups are D10, PSL(2,5), 32:D8, PΣL(2,9), PSL(2,13), and 24:S6. All these are well-known. For an odd number of vertices, these are the switching classes of the finite homogeneous graphs with primitive automorphism groups (I don’t think this is more than a small-number coincidence). On an even number of vertices, they all have doubly transitive automorphism groups, and are among the list of such things given by Don Taylor a long time ago.

The proof that the list is finite comes by confronting upper bounds for orders of primitive groups derived from CFSG with lower bounds from the assumption that every graph in the switching class possesses a non-trivial automorphism. By pushing these arguments as hard as possible, Pablo was able to show that there were no examples on more than 32 points, and I was able to search all the primitive groups with degree up to 32 and come up with the list.

I hope we will have a paper available quite soon.

One interesting thing emerged from the investigation, which is probably worth a further look. For reasons I won’t go into here, it suffices to consider the case where the number of vertices is even. (The odd case is covered by the results of Ákos Seress that I discussed in the earlier post.) The switching classes with primitive automorphism group on n vertices, with n even and n ≤ 32 fall into two types:

  • those with doubly transitive groups, which are in Taylor’s list; and
  • some with very small groups: two on 10 vertices with group A5, six on 28 vertices with group PGL(2,7), and six more on 28 vertices with group PSL(2,8).

I’d never seen anything like the second type before, so I looked at the first two examples, on 10 points.

The action of A5 is on the 2-element subsets of the domain {1,…,5}, which we can think of as edges of a graph. The orbits of the symmetric group S5 are isomorphism classes, of which there are just four with 3 edges, namely K3, K2P3, K1,3 and P4, where K means complete (or complete bipartite) graph and P means path, the subscript being the number of vertices. You can check that every 4-edge graph contains an even number of copies of P4, so these form a two-graph containing S5 in its automorphism group. The full automorphism group is larger; it is the group PΣL(2,9) (aka S6) and appears on our list.

However, the automorphism group of P4 consists of even permutations, so under the action of A5, the 60 copies of this graph fall into two orbits of 30. The table below shows the numbers of graphs in the various A5-orbits which are contained in each of the four-edge graphs on five vertices.

Graphs with 3 or 4 edges

You can see from the table that taking one of the A5-orbits on P4s, together with the orbit on K1,3s, form a two-graph. So here are the mysterious two switching classes with automorphism group A5. We see that their symmetric difference is the much more symmetric two-graph consisting of all the P4s.

Surely the examples on 28 points also have some nice structure! And what happens beyond?

Posted in exposition, mathematics | Tagged , , , , , | Leave a comment

Spitalfields photos

Take a look at these astonishing photographs …

http://spitalfieldslife.com/2014/06/29/an-astonishing-photographic-discovery/

Posted in history | Tagged , | 1 Comment

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.

Posted in exposition, mathematics | Tagged , , , , | Leave a comment

Metrics

HEFCE had a consultation on metrics. I found out about it too late to send in a submission.

But you may want to read what two people whose opinions I respect, David Colquhoun and David Spiegelhalter, have to say.

Posted in Uncategorized | Tagged , , , | 1 Comment

Busy times, 10: in Waterloo

After a week in London, off to Waterloo for Chris Godsil’s 65th birthday conference.

The week at home was no holiday: among other things I managed to

  • read and examine Christopher Harden’s PhD thesis (a nice study of fixed point polynomials of permutation groups);
  • write a talk for the Waterloo conference, and most of a talk for the
    Portuguese Mathematical Society summer meeting, from scratch;
  • make my annual foray to Oxford Street for clothes shopping (this didn’t get done last year, I was too busy, and having to divide my clothes between two places meant things were getting rather desperate);
  • go on an expedition to the dinosaurs in the Natural History Museum with my children and grandchildren.

A couple of nice speculations from Christopher Harden’s thesis (I don’t think he would call them conjectures unless he were feeling extremely optimistic; but he worked many examples and these speculations appear to hold). The fixed point polynomial of a permutation group is the generating function for the number of fixed points of elements of the group; that is, the coefficient of xm is the number of group elements with m fixed points.

  • The number of real roots of the fixed point polynomial of a transitive permutation group is bounded above by an absolute constant.
  • The roots of fixed point polynomials for arbitrary permutation groups are dense in the complex plane (not true for transitive groups, he found a zero-free region).

Then an early start on Sunday morning in order to catch a 10:40 flight from
Gatwick to Toronto.

I was delighted to be asked to speak, although I have no formal connection with Chris; much to people’s surprise, we don’t even have a joint paper. (Plenty of time yet! As far as the photography session before the conference banquet was concerned, what I share with Chris is being aged 65+ and being Australian/New Zealander.) But we have enough common interests that I felt I had things to say about graph endomorphisms and synchronization that would be interesting to him and his students and postdocs; I hope that proved to be the case.

With Chris Godsil

The conference was in the quantum nano centre, which seems to be practical as well as theoretical: is this the kit needed to build a quantum computer?

Building a quantum computer

It was a wonderful occasion, a very happy conference, which is a tribute to the esteem in which Chris is held by colleagues and present and former students. I first met Chris in 1980 (if I recall correctly): I was visiting Sydney, and he and Brendan McKay invited me down to Melbourne to work together for a few days. So it seems that I had known him for longer than most people at the meeting (Brendan, Cheryl Praeger and Wilfried Imrich excepted).

The front wall of the lecture room under the projector screen was one huge whiteboard – but the pens were not good enough to risk a board talk. The very left of the board was reserved for information; the first item concerned “collaboration space”, a room in another building where people could go to work together. I suggested that the term might be interpreted as “collaboration graph with extra structure”, e.g. with a simplex pasted on for every set of authors who have written a paper together (or should we require that to form a simplex it would have to be the case that every subset of those authors should have a paper together? I think not, since this requirement is not enforced for the graph.)

A lot of good talks too, some of which I will try to describe briefly.

  • Brendan McKay talked about his result on counting k-regular graphs with 1-factorisation. This is new, but Brendan and Chris did the bipartite case (aka counting Latin rectangles) long ago, and some of Chris’ tricks are useful here too.
  • Gordon Royle gave a summary of results about roots of chromatic polynomials. Since the Newton Institute programme in 2008, much of this wasn’t new to me, but the pictures really add something to the results.
  • There were several talks on perfect state transfer in quantum random walks on graphs. This seems to be a relatively rare phenomenon, each new example being something to take note of.
  • On a related theme, Chris himself talked about perfect mixing in quantum random walks. This is in some sense the reverse. Instead of wanting the wave function concentrated at a single vertex at some time, you want the probabilities evenly spread over all vertices. This is almost as rare. The only cycles known to have the property are those of lengths 3 and 4. It is known that there are no other even cycles, but the proof of this apparently simple fact requires tools as deep and devious as the Gel’fond–Schneider theorem on the transcendence of ab for algebraic numbers a and b (if the latter is irrational) and an analytic theorem of Haagerup. As he said, new tools needed! Akihiro Munemasa followed up with a talk about finding some examples (aka complex Hadamard matrices in 3-class association schemes). He also explained the array of antipodean animals on the front of the conference programme.
  • A couple of authors including David Roberson and Simone Severini talked about graph parameters lying between the clique number and the chromatic number (and so potentially useful in the synchronization project).
  • Although I had heard part of it before, I really liked Bojan Mohar’s talk about median eigenvalues of graphs (especially bipartite graphs). He took us right from Hückel’s molecular orbital theory (which, using an approximate version of Schrödinger’s equation, reduces analysis of aromatic hydrocarbons to a problem on eigenvalues of graphs) to recent results on the “median gap”. An interesting speculation was whether there could be a carbon molecule with the configuration of the Heawood graph (a kind of super-buckyball). Apparently such a molecule would have metal-like properties.
  • Marston Conder talked about “Extreme graph symmetries”, which sounds like a new sport for the daredevil mathematician.
  • Cheryl Prager told us how much of her joint work with Chris had involved asking questions about doubly transitive groups which could not be answered just by having a list of the groups available – these included distance-transitive graphs, imprimitive rank 3 groups, and neighbour-transitive codes in the Johnson schemes. I certainly agree that there are many more problems hiding here, as in some of my work with João Araújo.

My slides are in the usual place.

Herons

For the excursion, we went to Elora, where the Grand River flows through a spectacular gorge. Ian Wanless and I went for a walk along the gorge, and came back to look at a map in the tourist information (which suggested some much less interesting walks). Then we had lunch in a pub, coffee in another, and a beer in a third, until it was time to go.

Posted in events | Tagged , , , , , , , | 2 Comments

A five-finger exercise

This morning at the Godsil 65 conference, Cheryl Praeger was wearing a T-shirt she was a bit ashamed of. It had been produced by the Australian Mathematics Trust to commemorate Niels Abel’s anniversary, and featured a quintic equation (he was the mathematician who first showed conclusively that the quintic is not soluble by radicals). Unfortunately the quintic they had chosen has an integer root!

So here is my suggestion for a problem which should be easy if you have done any Galois theory. The other thing Abel is remembered for is abelian groups, so why not an irreducible quintic with abelian Galois group?

Exercise: Find a simple example of such a quintic.

Posted in Uncategorized | Tagged , , | 4 Comments

Almost highly transitive

I want to discuss a concept I have known about for quite a long time, but never found any real use for. Suggestions welcome!

Highly transitive groups

A permutation group is n-transitive if it has a single orbit on the set of n-tuples of distinct elements from its domain; it is highly transitive if it is n-transitive for all natural numbers n. (This concept, of course, applies only to infinite permutation groups.)

Apart from the symmetric group, and the finitary symmetric group, there are very many examples; many additional properties can also be required.

Almost highly transitive groups

The context is measure theory: we have a probability space X (a measure space of total measure 1). As usual, we say that something happens “almost everywhere” if it is true on a set of measure 1 (that is, everywhere except for a null set).

We say that a group G of measure-preserving transformations of X is almost transitive if it has an orbit (necessarily unique) of measure 1. More generally, G is almost n-transitive if it has an orbit of measure 1 on Xn (the set of n-tuples of elements of X, with the product measure); and G is almost highly transitive if it is almost n-transitive for all natural numbers n.

First example: graphs

There is a natural measure on the set of all graphs on a given countable vertex set V, described by the phrase “choose edges independently with probability 1/2″. More formally, we give measure 1/2n(n−1)/2 to the set of graphs which induce a given finite graph on a given n-element subset of V, and extend to the Borel sets (or the Lebesgue-measurable sets) in the standard way. The symmetric group on the set V acts as a group of order-preserving transformations of this space.

The Erdős–Rényi theorem (see here), asserting that a specific graph R (the “random graph” or “Rado graph”) occurs – up to isomorphism – with probability 1, shows that Sym(V) is almost transitive: isomorphisms are induced by elements of the symmetric group.

Now choose n graphs independently at random from this probability distribution. There are 2n possibilities for the structure of a pair of vertices, since they may be an edge or a non-edge in each of the n chosen graphs. The Erdős–Rényi argument, almost unchanged, says that a unique structure arises with probability 1.

Thus the action os Sym(V) on the space of graphs is almost n-transitive for all n, that is, almost highly transitive.

Orders

Now consider the same group Sym(V) for a countable set V, acting on the set of total orders of V.

How do we choose a total order at random? One way is to enumerate the points of V, as v1, v2, …, and order them in stages. Suppose that, after n stages, the first n points have been ordered. Then they give n+1 “intervals”: before the smallest, between the smallest and the second smallest, …, after the largest; assign the (n+1)st point randomly to one of these intervals, all intervals equally likely.

A calculation shows that this measure can also be described by saying that, given any n points, all n! orderings are equally likely. (There is something to prove since the n points may not be the first in the enumeration.) This description shows that Sym(V) does indeed act as a group of measure-preserving transformations.

Perhaps not surprisingly, a random order is isomorphic to the order of the rational numbers with probability 1. By Cantor’s theorem, this is the unique dense order without endpoints on a countable set, so it suffices to show that the random order is dense and without endpoints with probability 1. By the usual argument invoking the fact that a countable union of null sets is null, it suffices for density to prove that given two points y and z, conditional on y < z, the probability that no point lies between y and z is zero.

But we can compute this probability. Starting at stage n (assuming that by this stage we know that y is smaller than z and no point lies between), the probability that no subsequent point is put into this gap is

(1-1/(n+1))(1-1/(n+2))… = 0

(the infinite product diverges).

The proof that there is no least or greatest element is similar.

So we have established that Sym(V) is almost transitive on the set of orders.

The proof that it is almost n-transitive involves a small subtlety, which held me up for a while. The object we should get if we choose n orders independently is the unique countable homogeneous universal n-order (described here). But the calculation similar to the one I did above is much more difficult.

The trick is as follows. I describe the case n = 2 (biorders) here; the general case is similar.

Another way to describe the countable dense order without endpoints is as follows. Sample countably many points from the uniform distribution on the open unit interval. The denseness and absence of endpoints are easily shown by simple arguments involving geometric probability.

Now we see that choosing two such orders is equivalent to sampling countably many points from the open unit square. Once again the defining property of the universal homogeneous biorder is easily verified.

So, indeed, Sym(V) is almost highly transitive on the set of orders on V.

Triangle-free graphs

There is a nice triangle-free graph (countable, universal, homogeneous), namely Henson’s graph. I struggled for years to find a similarly nice measure which gives the isomorphism class of Henson’s graph measure 1; the difficulty arises because triangle-free graphs have a very strong tendency to be bipartite (the Erdős–Kleitman–Rothschild theorem). The problem was solved by Petrov and Vershik, as I described here.

So Sym(V) acts as measure-preserving transformations of the space of all graphs on the vertex set V, with the Petrov–Vershik measure, and the action is almost transitive; the unique orbit of measure 1 is the isomorphism class of Henson’s graph.

Problem: Is this action almost highly transitive?

Footnote: Baire category

If G acts by isometries on a complete metric space, there is an analogous notion of “almost transitive”: G is almost transitive if it has an orbit which is residual (contains a countable intersection of open dense sets). Then we can make a similar definition of “almost highly transitive”.

As usual in this game, the Baire category notion is much better explored than the probabilistic notion. In particular, many closed permutation groups (such as the symmetric group, and the automorphism group of the random graph) have the property that their actions on themselves by conjugation is almost highly transitive: that is, there is a generic element (whose conjugacy class is residual), and indeed, for any n, a generic n-tuple of elements. These facts play an important role in the proof of the strong index property for these groups.

Posted in Uncategorized | Tagged , , , , , , , | 1 Comment