============================== Bar-Ilan Combinatorics Seminar ============================== The first meeting of the seminar this year will take place, IYH, on (when) Tuesday, 11 Marcheshvan (Oct. 23) refreshments at 11:45, talk at 12:00 noon (where) Room 331 (Math Dept Seminar Room), Math and CS Building (216), Bar-Ilan University (who) Avraham Trakhtman (Bar-Ilan University) will talk about (what) "The road coloring problem" Abstract: --------- The synchronizing word of a deterministic automaton is a word in the alphabet of colors (considered as letters) of its edges that maps the automaton to a single state. A coloring of edges of a directed graph is synchronizing if the coloring turns the graph into a deterministic finite automaton possessing a synchronizing word. The road coloring problem is the problem of synchronizing coloring of a directed finite strongly connected graph with constant outdegree of all its vertices if the greatest common divisor of lengths of all its cycles is one. The problem was posed by Adler, Goodwyn and Weiss over 30 years ago and evoked noticeable interest among the specialists in the theory of graphs, deterministic automata and symbolic dynamics. The problem is described even in "Vikipedia" - the popular Internet Encyclopedia. A positive solution of the road coloring problem is presented. Forthcoming Events ================== * 18 Marcheshvan (Oct. 30) Shelly Garion (Hebrew University): "Commutator maps, measure preservation and T-systems" * 25 Marcheshvan (Nov. 6) Avital Frumkin (Tel-Aviv University): "Asymptotic Kronecker coefficients for hook diagrams" ************************************************************************* You are all invited ! (Graduate students especially welcome) If you want to give a talk at the seminar, or know a prospective speaker, please contact Ron Adin . Seminar's homepage: see *************************************************************************