Title: The chromatic number of random Cayley graphs
Speaker: Noga Alon, IAS
Date: Tuesday, December 6, 2011 2:00pm
Location: Hill Center, Room 425, Rutgers University, Busch Campus, Piscataway, NJ
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, focusing on the question of estimating the chromatic number of a random Cayley graph of a given group with a prescribed number of generators. One representative result is the fact that if p is a large prime and S is a random subset of at most 0.5 log_2 p members of Z_p, then the chromatic number of the Cayley graph of Z_p with respect to S is almost surely exactly 3, whereas if T is a random subset of at least 1.01 t and at most 2.99 t elements of Z_2^t, then the chromatic number of the Cayley graph of Z_2^t with respect to T is almost surely exactly 4.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math