Title: Ramsey Cayley graphs, random graph models, and information theory
| Speaker: | Jacob Fox |
| Affiliation: | Stanford University |
| Location: | MC 5501 |
Abstract: A graph is Ramsey if its largest clique or independent set is of size logarithmic in the number of vertices. While almost all graphs are Ramsey, there is still no known explicit construction of Ramsey graphs. Alon conjectured that every finite group has a Ramsey Cayley graph. We prove that for almost all n, all abelian groups of order n satisfy Alon's conjecture. We also verify a conjecture of Alon and Orlitsky motivated by information theory that there are self-complementary Ramsey Cayley graphs. We further prove general results for clique numbers of random graph models. Along the way, we study some fundamental problems in additive combinatorics, and discover that group structure is superfluous for these problems. Based on joint work with David Conlon, Huy Pham, and Liana Yepremyan.