Department of Mathematics

Address: Mathematics 253-37 | Caltech | Pasadena, CA 91125
Telephone: (626) 395-4335 | Fax: (626) 585-1728
Math Home | People | Seminars | Courses | Undergraduate Info | Graduate Program | Positions
Project MATHEMATICS! | Caltech Home

The 20th Annual Charles R. DePrima Memorial
Undergraduate Mathematics Lecture
Wednesday, November 17, 2010
4:15 p.m.  151 Sloan

Benjamin Weiss
  Institute of Mathematics    
    Hebrew University of Jerusalem

  The Road Coloring Problem and Symbolic Dynamics

Abstract:  Starting with a network consisting of a finite number of cities and one way roads connecting some of them with exactly d roads exiting from each city a "coloring" is an assignment of distinct colors to the roads exiting from each city. The coloring is "synchronizing" if there is a finite sequence of these colors W so that if people start at all of these cities at the same time and follow the directions W at the end all people will find themselves in the
same city. 

   The road coloring problem asks whether the obvious necessary conditions for the existence of such a synchronizing coloring are also  sufficient.  The problem was raised over forty years ago, in connection with the classification of shifts of finite type in symbolic dynamics, and after being open for many years was  solved quite recently by A. Trahtman.

 I plan to explain the problem, its history and solution as well some of the dynamical background.

Dr. Weiss received his Ph.D. in Mathematics from Princeton University in 1965. The numerous honors bestowed on him include the 2006 Rothschild Prize, membership in the American Academy of Sciences, Plenary Lecture at the IEEE conference on Information Theory in 2001, and an invited lecture at the 1974 ICM. Professor Weiss is well known for giving excellent lectures to a broad mathematical audience. His prominent lecture series include the Porter Lectures at Rice University in 1998 and the Karel deLeeuw Memorial Lectures at Stanford in 2006.

The Charles R. DePrima Memorial Undergraduate Mathematics Lecture was established by a gift from Charles R. DePrima and Margaret Thurmond DePrima. The Institute is privileged to honor the memory of Professor DePrima and his distinguished contribution to mathematics and Caltech, where he served as a faculty member for over forty years, with a lecture each year by an outstanding mathematician. Professor DePrima perceived that there were few or no special talks or seminars designed for undergraduates; he and Margaret DePrima intended that this lecture series would fill that need.

  | © California Institute of Technology | Questions?  scroomes @