### Rutgers Discrete Mathematics Seminar

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

Abstract:
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