Coloring random Cayley graphs

School of Mathematics Colloquium
Thursday, September 6, 2012 - 11:00
1 hour (actually 50 minutes)
Klaus 1116
Tel Aviv Uniersity
The study of random Cayley graphs of finite groups is related to the investigation of Expanders and to problems in Combinatorial Number Theory and in Information Theory. I will discuss this topic, describing the motivation and focusing on the question of estimating the chromatic number of a random Cayley graph of a given  group with a prescribed number of generators. The investigation of this problem combines combinatorial, algebraic and probabilistic tools. Several intriguing questions that remain open will be mentioned as well.