Around the Cerny conjecture

Speaker: Peter P. Palfy (Alfred Renyi Institute of Mathematics,
Hungarian Academy of Sciences)

Abstract: A famous open problem in automata theory is the half-a-century old Cerny conjecture. In common mathematical terms it can be formulated in the following way. Let us given some transformations (self-maps) of an n-element finite set. Assume that some composition of the given transformations is a constant map. The Cˇerny ́ conjecture asserts that there is a composition with at most (n−1)^2 factors that yields a constant map. The best known upper bound is cubic in n, it is based on a combinatorial result of Peter Frankl. I will outline a possible strategy that might lead to an improved upper bound (although it will not be suitable to prove the conjecture). I will pose some analogous group theoretic questions as well.