Видеотека: П. Д. Камерон, Synchronization and Semigroups, Graphs and Groups

ВИДЕОТЕКА


Конференция международных математических центров мирового уровня 9 августа 2021 г. 14:40, г. Сочи

Synchronization and Semigroups, Graphs and Groups П. Д. Камерон University of St Andrews
Аннотация: An automaton is synchronizing if there is a word $w$ in its alphabet (called a reset word) such that, when the machine reads $w$, it ends up in a fixed state, independent of its starting state. As well as practical applications, research on this has been driven by the infamous Černý conjecture, which asserts that, if an $n$-state automaton is synchronizing, then it has a reset word of length at most $(n-1)^2$. If true, this would be best possible; but we still lack a proof. I will not be talking about the Černý conjecture. I begin by translating the synchronization question into one about transformation monoids. Each input letter for the automaton defines a transformation on the set of states, and concatenating words corresponds to composing the corresponding transformations. Thus an automaton can be regarded as a transformation monoid with a specified generating set. The automaton is synchronizing if and only if the monoid contains a transformation of rank $1$, that is, one whose image is a singleton. Now a monoid fails to be synchronizing if and only if it is contained in the endomorphism monoid of a graph on its domain, and the graph can be chosen to have clique number equal to chromatic number. This seems a complicated way to check synchronization (which can be done in polynomial time), but has great theoretical importance. For some time, with João Araújo and many others, I have been investigating the synchronization question for monoids generated by a permutation group and one further transformation. (I note in passing that the extremal examples known for the Černý conjecture have this form.) A natural first question is: \begin{quote} Which permutation groups $G$ have the property that, for any transformation $t$ which is not a permutation, the monoid $\langle G,t\rangle$ is synchronizing? \end{quote} We use the term synchronizing for a permutation group with this property, by abuse of language (a permutation group of degree greater than $1$ is never synchronzing as a monoid). Using the earlier result, it can be shown that $G$ is synchronizing if and only if there is no $G$-invariant graph with clique number equal to chromatic number. It is easy to show that synchronizing permutation groups must be transitive and primitive, and cannot preserve a Cartesian decomposition of the domain. According to the O'Nan–Scott Theorem, such groups must be affine, diagonal, or almost simple. In each of these classes, some groups are synchronizing and some are not. But there has been recent progress. Diagonal groups of dimension at least $2$ are non-synchronizing, though recently synchronizing examples of dimension $1$ have been found. In the case of almost simple groups, the synchronizing examples mostly depend on constructions in finite geometry and design theory. I will survey as much of this beautiful theory as time permits.