Synchronization and separation in the Johnson schemes

Today a paper by Mohammed Aljohani, John Bamberg and me went on the arXiv on this topic.

Here is a brief summary of what it is about. Synchronization comes in several flavours, and the point of the paper is to extend this a little further.

• Automata: a finite deterministic automaton is synchronizing if there is a string of symbols in its alphabet (called a reset word such that, after reading this word, it is in a known state, independent of its starting state.
• Semigroups: Regarding the transititions of the automaton as maps on the set of states generating a semigroup, the equivalent definition is that a transformation semigroup is synchronizing if it contains an element whose rank (the cardinality of the image) is 1.
• Permutation groups: A permutation group of degree greater than 1, regarded as a semigroup, is clearly not synchronizing. So we re-use the word with a different meaning and say that the permutation group G is synchronizing if, for every map a on the domain which is not a permutation, the semigroup generated by G and a is synchronizing. Now it is known that this property of Glies between primitivity (no nontrivial invariant equivalence relation) and 2-homogeneity (no nontrivial invariant symmetric binary relation).
• Now it can be shown that a transformation semigroup fails to be synchronizing if and only if it is contained in the endomorphism semigroup of a nontrivial (not complete or null) graph whose clique number and chromatic number are equal; and a permutation group fails to be synchronizing if and only if it is contained in the automorphism group of a graph with these properties.
• Association schemes: An association scheme is a partition of the edge set of the complete graph into subgraphs whose adjacency matrices have the property that their linear span is closed under multiplication. (This has a combinatorial interpretation, which is a bit hard to state.) Now we say that an association scheme is non-synchronizing if some non-trivial union of graphs in the scheme has clique number equal to chromatic number, and synchronizing if not.

There is a closely related condition, which has no simple interpretation in the context of automata or semigroups (as far as I know). It depends on the following observations:

• Let G be a transitive permutation group on a finite set X, and A and B subsets of X with |Ag∩B| ≤ 1 for all g∈G. Then |A|.|B| ≤ |X|.
• Let Γ be a union of graphs in an association scheme. Then the product of the clique number and independence number of Γ is at most the number of vertices.

The second result is due to Delsarte, in his celebrated PhD thesis from Louvain in which he developed important techniques for studying the size of cliques and independent sets in graphs in association schemes, and applied the results to obtain bounds in coding theory and design theory.

Thus we call a transitive permutation group non-separating if there are subsets A and B of the domain, each larger than 1, with the product of their sizes being the degree and any translate of A meeting B in a single point; G is separating otherwise. It can be shown that a transitive permutation group is non-separating if and only if there is a non-trivial G-invariant graph in which the product of the clique number and the independence number is equal to the number of vertices.

Similarly, an association scheme is non-separating if some non-trivial graph in the scheme attains Delsarte’s bound (that is, clique number times independence number equals number of vertices), and separating if not.

In either case, separating implies synchronizing.

The main question we address in the paper is:

Question: Let G be the symmetric group of degree n in its action on the set of k-subsets of {1,…,n}. For which values of n and k is it the case that G is synchronizing? separating?

This is equivalent to asking, for which n and k is the Johnson association scheme J(n,k) synchronizing or separating. Note that, replacing k-sets by their complements if necessary we may assume that n ≥ 2k. In the case n = 2k, the group or scheme is imprimitive: “equal or disjoint” is a non-trivial equivalence relation. So we can assume that n ≥ 2k+1.

Now a small detour. Assume that 0 < t < k < n. A Steiner system S(t,k,n) consists of a collection of k-subsets of an n-set with the property that any t-subset is contained in a unique subset in the collection. The blocks of a Steiner system form a clique in the graph (in the Johnson scheme) in which two sets are joined if they intersect in fewer than t points. Now we can always find an independent set in this graph, by considering all the k-sets containing a fixed t-set. (This is said to be of EKR type: the famous Erdős–Ko–Rado theorem says that, if n is sufficiently large in terms of k, this is the largest coclique in this graph.) Now it is not a difficult exercise to show that the product of the number of blocks in a Steiner system and the size of the EKR coclique is equal to the total number of k-sets. So, if a Steiner system exists, then the Johnson scheme is non-separating.

Our main conjecture is that the converse is true asymptotically:

Conjecture: There is a function F such that, if n ≥ F(k), then the Johnson scheme J(n,k) is non-separating if and only if there exists a Steiner system S(t,k,n) for some t with 0 < t < k.

This conjecture synchronizes well with the great result of Peter Keevash, discussed here. There are divisibility conditions which are easily shown to be necessary for the existence of a Steiner system; Keevash showed that they are asymptotically sufficient, in the sense that, for large enough n, if the divisibility conditions are satisfied, then the Steiner system exists. So, in our main conjecture, we can replace “there exists a Steiner system” by the apparently much weaker condition “the divisibility conditions for a Steiner system are satisfied”.

What about synchronization? A large set of Steiner systems is a partition of the set of all k-sets into Steiner systems. If a large set of Steiner systems exists, then the Johnson scheme is not synchronizing. Again, our conjecture is that the converse holds asymptotically; for large enough n (in terms of k), synchronization can only fail because of the existence of a large set of Steiner systems.

For small n, other interesting things can happen. Consider, for example, the case n = 7, k = 3. The lines of the Fano plane form a set of seven 3-sets, any two meeting in one point, that is, a clique in the graph where two sets meet if they intersect in one point. We get a colouring of this graph with 7 colours as follows. For each line of the Fano plane, the five sets consisting of this line and the four 3-sets disjoint from it form an independent set, and this gives a partition into seven independent sets of size 5, the required colouring. So J(7,3) is non-synchronizing.