Latest News
2010 NCTS Short Course on Discrete Mathematics-Topics on Synchronization ( 2010-12-13 )
News Content:
Speaker: Prof. Peter J. Cameron (Queen Mary, University of London) Time: PM 2:00-4:00, 12/23 (Thu), 12/28 (Tue.), 12/30 (Thu.), 1/4 (Tue.) Place: Lecture Room B, NCTS, 4thFloor, The 3rdGeneral Building, National TsingHuaUniversity Description: A (finite-state deterministic) automaton is synchronizing if there is a sequence of transitions which brings the automaton to a fixed state from an arbitrary starting point; in other words, the monoidgenerated by the transitions of the automaton contains a constant function. Such a sequence is called a reset word. The celebrated conjecture asserts that if an n-state automaton has a reset word, then it has one of length at most . An approach to this conjecture (not so far successful!), suggested by Ben Steinberg and , brings together automata theory, permutation groups, representation theory, graph homomorphisms, extremalcombinatorics, and finite geometry. The course will introduce the various topics mentioned above and explain some of their connections. An outline follows. Automata: Synchronization, the conjecture, the road-colouringconjecture and its proof, applications to industrial robotics and biocomputing. Permutation groups: Transitivity, primitivity, 2-transitivity, the O’Nan–Scott Theorem, classification of 2-transitive groups (using CFSG). Synchronizing groups: Primitivity, examples, separation properties, non-synchronizing ranks of a permutation group. Examples: Actions of symmetric groups (involving extremalcombinatorics: Baranyai’sTheorem, large sets of Steiner triple systems) and classical groups (involving finite geometry: ovoids, fans and spreads of classical polar spaces). Graph homomorphisms: Hom-equivalence, core and hull of a graph, characterization of synchronization and separation in terms of actions on graphs, relation with constraint satisfaction. Representation theory: Permutation representation, QI groups and their classification.
go back