Around the Cerny conjecture

Type: 
Lecture
Audience: 
Open to the Public
Building: 
Zrinyi u. 14
Room: 
301
Wednesday, February 11, 2015 - 2:00pm
Add to Calendar
Date: 
Wednesday, February 11, 2015 - 2:00pm to 3:00pm

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 Cern´y 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.