Road closures and idempotent-generated semigroups

Guardbridge roadworks

The University of St Andrews is installing a biomass boiler, to provide hot water to heat University buildings, on the old paper mill site at Guardbridge. The water has to be piped four miles to St Andrews, and this big job has involved a lot of road closures this year, which hasn’t made life easy for people travelling around here, between St Andrews and Leuchars station or Dundee, for example.

However, it was always possible to get through, by taking a sufficiently devious route.

This is a metaphor for the problem that João Araújo and I are thinking about at the moment; our paper has just appeared on the arXiv. I will tell the story first without the motivation, but wait, that will come later.

Let G be a transitive permutation group on a set X. The orbital graphs for G are the graphs with vertex set X, whose edge sets are orbits of G on the set of 2-element subsets of X. So by definition these graphs are both vertex-transitive and edge-transitive – nice properties for a network! Moreover, if G acts primitively on the vertex set X, then every orbital graph is connected.

However, the action of G on the set E of edges of an orbital graph may or may not be primitive. For each maximal block of imprimitivity B in this action, consider the graph obtained by removing the edges in B from E. This graph may or may not be connected.

Here is an example. Take G to be the automorphism group of the m×m grid (the graph with edges joining pairs of vertices in the same row or in the same column of the grid). Then G acts primitively on vertices, but not on edges; the edges fall into two blocks of imprimitivity, the horizontal edges and the vertical edges. If we dig up all the vertical edges, then it is not possible to travel from one row to another; the resulting graph is disconnected.

However, if G acts primitively on the edge set E, for example, then a maximal block consists of a single edge; and it is easy to see that removing one edge from a vertex- and edge-transitive graph with more than two vertices cannot disconnect it.

Let us say that a transitive permutation group G has the road closure property if, for every orbital graph (X,E) and every maximal block of imprimitivity for G acting on E, the graph (X,EB) is connected. Which groups have this property? Here is what we know.

  • If G is imprimitive, then it does not have the road closure property.
  • If G is primitive but not basic (this means that X has the structure of a Cartesian power Ad which is preserved by G, so that G is embedded in a wreath product), then it does not have the road closure property. The square grids above are the paradigm for this.
  • If G is primitive and basic, but has an imprimitive normal subgroup of index 2, then it does not have the road closure property. This rules out groups of automorphisms and dualities of various incidence structures, acting on the set of flags of the structure: such structures include points and hyperplanes (or points and complements of hyperplanes) in projective spaces, points and lines in some generalised polygons, points and blocks in some symmetric designs. There are other non-geometric examples arising from groups like PGL(2,q) for certain congruences on q.
  • We have another class of examples, built using the wonderful geometric phenomenon of triality for the quadrics associated with split quadratic forms in 8-dimensional space. The smallest example is a primitive group of degree 14175.

Conjecture: A transitive permutation group has the road closure property if and only if it is primitive and basic, does not have an imprimitive normal subgroup of index 2, and is not one of our examples built from triality.

The conjecture says that most primitive basic groups have the road closure property.

We have tested the conjecture computationally, and found that it holds for primitive groups with degree up to 130. (The basic primitive groups without the road closure property in this range have degrees 21, 28, 45, 52, 55, 66, 105, 117 and 120.) We have also checked various degrees beyond 120. In addition, we have shown that various classes of primitive groups do have the road closure property: these include 2-transitive and 2-homogeneous groups, transitive groups of prime or prime squared degree, and symmetric and alternating groups Sm and Am, acting on the set of k-element subsets of their domains, with m > 2k.

Of course it must be said that the limit of our computation is very small compared, for example, to the degree of the smallest example arising from triality.

But why would we want to prove such a theorem?

Our big project consists of investigating properties of the semigroups formed in the following way: take a permutation group G and a non-permutation a, form the semigroup generated by G and a, and then remove the elements of G, to leave a semigroup of singular maps.

One important property a semigroup may have is being generated by idempotents. We have various results on this. (For example, if the above semigroup is idempotent-generated for every choice of a map of rank k, where k ≥ 6 and n ≥ 2k+1, then G must be the symmetric or alternating group. (I will say more about the case k > 2 in a later post.) But the particular connection relevant here is the following.

Theorem: Let G be a transitive permutation group on X. Then the following conditions are equivalent:

  • for any map a of rank 2, (that is, one whose image has cardinality 2), the semigroup ⟨G,a⟩\G is idempotent-generated;
  • G has the road closure property.

There are exponentially many maps of rank 2, since we have to choose an arbitrary subset of the domain to map to the first image point. The advantage of our characterisation of the road closure property in combinatorial terms is that the calculation involved is much smaller. There is at most a linear number of orbital graphs; the numbers of maximal blocks are hopefully not too large; and connectedness is very fast to check. Indeed, some of our intermediate results mean that certain classes of groups (non-basic groups, 2-homogeneous groups, groups of prime degree) don’t even need to be checked.

At this point another question might occur to you.

Is the number of maximal blocks of imprimitivity through a point for a transitive group G of degree n bounded above by a polynomial of degree n? Find the best bound!

A special case of this problem has a long history. In 1961, Tim Wall conjectured that the number of maximal subgroups of a finite group of order n is not more than n. Now any group has a regular action (as in Cayley’s theorem), which is transitive; the blocks of imprimitivity containing the identity are just the maximal subgroups. So Wall’s conjecture is a special case of the problem above when the permutation group is regular. Wall’s conjecture was disproved by the participants in an AIM workshop a few years ago, but it is thought to be very nearly true; in particular, Martin Liebeck, Laszlo Pyber and Aner Shalev showed that the number of maximal subgroups is bounded by a constant times the 3/2 power of the group order.

So if you are interested in permutation group theory, the problem of avoiding closing a block of roads and disconnecting the graph is not only theoretically attractive, but comes with a ready-made application; and the use of triality to construct examples is particularly delightful!


About Peter Cameron

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

Leave a Reply

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

You are commenting using your 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