The EMS Publishing House is now EMS Press and has its new home at

Please find all EMS Press journals and articles on the new platform.

Portugaliae Mathematica

Full-Text PDF (142 KB) | Metadata | Table of Contents | PM summary
Volume 74, Issue 3, 2017, pp. 213–232
DOI: 10.4171/PM/2003

Published online: 2018-02-08

Synchronization and separation in the Johnson schemes

Mohammed Aljohani[1], John Bamberg[2] and Peter J. Cameron[3]

(1) University of St Andrews, UK
(2) University of Western Australia, Perth, Australia
(3) University of St Andrews, UK

Recently Peter Keevash solved asymptotically the existence question for Steiner systems by showing that $S(t,k,n)$ exists whenever the necessary divisibility conditions on the parameters are satisfied and $n$ is sufficiently large in terms of $k$ and $t$. The purpose of this paper is to make a conjecture which if true would be a significant extension of Keevash’s theorem, and to give some theoretical and computational evidence for the conjecture.

We phrase the conjecture in terms of the notions (which we define here) of synchronization and separation for association schemes. These definitions are based on those for permutation groups which grow out of the theory of synchronization in finite automata. In this theory, two classes of permutation groups (called synchronizing and separating) lying between primitive and $2$-homogeneous are defined. A big open question is how the permutation group induced by $S_n$ on $k$-subsets of $\{1,\ldots,n\}$ fits in this hierarchy; our conjecture would give a solution to this problem for $n$ large in terms of $k$. We prove the conjecture in the case $k=4$: our result asserts that $S_n$ acting on $4$-sets is separating for $n\ge10$ (it fails to be synchronizing for $n=9$).

Keywords: Steiner system, association scheme, Johnson scheme, synchronization, separation, projective plane

Aljohani Mohammed, Bamberg John, Cameron Peter: Synchronization and separation in the Johnson schemes. Port. Math. 74 (2017), 213-232. doi: 10.4171/PM/2003