Huy Tuan Pham, Random Cayley graphs and Additive combinatorics without groups

A major goal of additive combinatorics is to understand the structures of subsets A of an abelian group G which has a small doubling K = |A+A|/|A|. Freiman’s celebrated theorem first provided a structural characterization of sets with small doubling over the integers, and subsequently Ruzsa in 1999 proved an analog for abelian groups with bounded exponent. Ruzsa further conjectured the correct quantitative dependence on the doubling K in his structural result, which has attracted several interesting developments over the next two decades. I will discuss a complete resolution of (a strengthening of) Ruzsa’s conjecture.

Surprisingly, our approach is crucially motivated by purely graph-theoretic insights, where we find that the group structure is superfluous and can be replaced by much more general combinatorial structures. Using this general approach, we also obtain combinatorial and nonabelian generalizations of classical results in additive combinatorics, and solve longstanding open problems around Cayley graphs and random Cayley graphs motivated by Ramsey theory, information theory and computer science.

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