Combinatorics Seminar 2018

Speaker: Peter Cameron, University of St Andrews

Date: Thu, Oct 04, 2018

Time: 10:00 - 11:00

Venue: Large Meeting Room

Title: Synchronization and separation in the Johnson schemes


The concept of synchronization in automata theory has been studied for over half a century, motivated by the infamous Černý conjecture. It can be translated into a problem in semigroup theory, and from there into graph theory: the obstruction to a transformation monoid being synchronizing is that it is contained in the endomorphism monoid of a non-null graph with clique number equal to chromatic number.

A natural question (to a permutation group theorist) is: which permutation groups $G$ have the property that, for any non-permutation $t$ of the domain, the monoid generated by $G$ and $t$ is synchronizing? By abuse of language we call such a permutation group synchronizing. Every synchronizing group is primitive, and any $2$-homogeneous group is synchronizing. We also consider a property of a permutation group of being separating, which has no easy translation into semigroup language but turns out to be a little stronger than the property of being synchronizing.

For the permutation group induced by the symmetric group $S_n$ on $k$-element subsets of $\{1,\ldots,n\}$, deciding whether it is synchronizing or separating leads to some hard problems in extremal combinatorics and design theory, including the Erdős--Ko--Rado theorem, Baranyai's theorem on factorisation of complete uniform hypergraphs, and Keevash's theorem on the existence of Steiner systems, as well as the Lu--Teirlinck theorem on large sets of Steiner triple systems.

This is joint work with Mohammed Aljohani and John Bamberg.

Slides: View slides