Computer Science/Discrete Mathematics Seminar I

Subsets $A$ of an abelian group with a small doubling $|A+A|/|A|$ have been extensively studied, and results of Freiman, Ruzsa and Green give fundamental structural descriptions of such sets. These have important applications across combinatorics and computer science, and have motivated the development of a number of influential techniques. 

In this talk, I will discuss a new combinatorial approach to several problems involving sets with small doubling. 

Over abelian groups where all elements have order at most $r$, the Freiman-Ruzsa theorem says that a set $A$ with $|A+A| \le K|A|$ is contained in a subgroup of size at most $O_{r,K}(|A|)$, and Ruzsa conjectured a tight dependence on $K$. In the first application, I will discuss a short complete resolution of Ruzsa’s conjecture. 

In the second application, we show that random functions give good sumset extractors in general (possibly nonabelian) groups. 

Surprisingly, our approach is crucially motivated by purely combinatorial graph-theoretic insights, where we find that the group structure is superfluous and can be replaced by much more general combinatorial structures. In particular, I will describe a further corollary, which is a combinatorial generalization of the Freiman-Ruzsa theorem over $\mathbb{F}_2^n$. 

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