Computer Science/Discrete Mathematics Seminar II

Topic: Random Cayley Graphs From a Combinatorial Perspective
Speaker: Huy Tuan Pham
Affiliation: Stanford University
Date: April 22, 2024

Cayley graphs provide interesting bridges between graph theory, additive combinatorics and group theory. Fixing an ambient finite group, random Cayley graphs are constructed by choosing a generating set at random. These graphs reflect interesting symmetries and properties of the group, at the cost of inducing complex dependencies.

I will discuss several results on clique and independence numbers of random Cayley graphs in general groups, progress towards a conjecture of Alon on existence of Ramsey Cayley graphs, and a proof of a conjecture of Alon and Orlitsky. These questions are naturally connected with some fundamental problems in additive combinatorics. Surprisingly, our insights suggest that in many of these problems, the group structure is superfluous and can be replaced by much more general combinatorial structures.

I will discuss the main general combinatorial models and ideas behind these results. I will also discuss how they relate to the additive combinatorial corollaries discussed in Monday’s talk.

Based on joint work with David Conlon, Jacob Fox and Liana Yepremyan.