A family of non-synchronizing groups

As I explained recently, according to the O’Nan–Scott Theorem, a finite primitive permutation group either preserves a Cartesian structure, or is of affine, diagonal or almost simple type. In all these types except the last, the action of the group is specified; the “almost simple” category remains the most mysterious.

There are a number of results which specifically concern almost simple primitive groups. Notably, there is a classification of these into “large” and “small” groups:

  • the large groups are symmetric or alternating groups acting on subsets of fixed size, or uniform partitions (partitions into parts of constant size) of th eire domain, or classical groups acting on an orbit of subspaces or complementary pairs of subspaces in their natural modules;
  • the small groups have bounded base size (at most 7, with equality only for the Mathieu group M24), and hence order bounded by a polynomial in the degree.

I desribed in the post cited above how we now know that a permutation group which is synchronizing but not separating must be primitive and almost simple. So it is natural to consider first the large groups (since these are well-specified groups with well-specified actions) and look among them for examples of this somewhat elusive class of groups. One infinite family (5-dimensional orthogonal groups over fields of odd prime order, acting on their quadrics) and two pairs of “sporadic” examples, are currently known.

I described here some work on the symmetric groups Sn acting on k-element subsets of the domain. In the paper, we give a nice conjecture that, asymptotically (that is, for n large compared to k), this group is non-separating if and only if a Steiner system on n points with block size k exists; by Peter Keevash’s result, this is equivalent to an arithmetic condition on n (it must belong to one of a set of congruence classes).

Leonard Soicher has produced a very efficient program for testing synchronization and separation for primitive groups. For degree 280, a lot of interesting things happen. One special case of this is that S9, acting on partitions into 3 sets of size 3, is non-synchronizing.

Inspired by this, I showed that, if n = kl, with k > 2 and l > 3, then Sn, acting on the set of partitions into l sets of size k, is non-synchronizing. The proof goes like this. Take the graph whose vertices are these partitions, two partitions adjacent if they have no common part. This graph is obviously invariant under the symmetric group. I claim that its clique number and chromatic number are equal. To see this, first take the colouring of the graph as follows. Choose an element x of {1,…,n}. For each (k−1)-subset A of the complement, assign colour cA to a partition P if the part of P containing x is {x}∪A. Clearly each colour class is an independent set, so we have a proper colouring. To find a clique with size equal to the number of colours, we use Baranyai’s celebrated theorem (proved using Max-Flow Min-Cut): the k-sets can be partitioned into classes, each of which is a partition of {1,…,n}. Of the resulting partitions, clearly no two share a part, and so they form a clique in the graph.

As explained in the earlier post, having a nontrivial G-invariant graph with clique number equal to chromatic number is equivalent to non-synchronization.

What is of some interest is that, unlike many proofs of non-synchronization, the construction of the colouring is elementary, while the clique requires heavier machinery.

This proof fails for partitions with just two parts, since then the graph constructed is complete. (If two 2-part partitions share a part, they are equal.) Indeed, the group S2k acting on partitions into two parts of size k is 2-transitive (and hence separating) for k = 2 and for k = 3; it is non-synchronizing for k = 4 and for k = 6, by constructions using the Steiner systems S(3,4,8) and S(5,6,12); it is separating for k = 5, shown by computation. So the picture is somewhat unclear!

Continuing, the next class of large almost simple groups is given by classical groups acting on the points of their associated polar spaces. These are non-separating if and only if the polar space contains an ovoid; they are non-synchronizing if and only if the polar space has either a partition into ovoids, or an ovoid and a spread. The question of existence of such structures is not completely settled, despite a lot of work by finite geometers. Note that our one known infinite family of synchronizing but not separating groups are of this type.

What about the small groups? At present we have no good methods for dealing with these. Is it possible that the smallness of base size or order can be used to decide these questions?

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, symmetric group 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 )

Google+ photo

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

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.