**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

**Abstract**:

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 beingseparating, 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