Synchronizing groups
11/11/2015 11 de Novembro – 16:00  sala 6.2.33
Peter Cameron (University of London, School of Mathematical Sciences)
Faculdade de Ciências da Universidade de Lisboa  Departamento de Matemática
An automaton is synchronizing if there is a reset word (a sequence of inputs) which brings it to a known state regardless of its initial state; in other words, the transformation monoid generated by the transitions of the automaton contains a constant map. Motivated by examples of synchronizing automata with the longest known reset word for a given number of states, we define a permutation group to be synchronizing if, together with any nonpermutation, it generates a constant map.
Synchronizing monoids and groups are closely related to graph endomorphisms, and techniques for studying them range over group theory, extremal combinatorics, representation theory, finite geometry, and other areas. I will give a somewhat selective survey of this.
