Coloring random Cayley graphs

Series: 
School of Mathematics Colloquium
Thursday, September 6, 2012 - 11:00
1 hour (actually 50 minutes)
Location: 
Klaus 1116
,  
Tel Aviv Uniersity
Organizer: 
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.