Printable PDF
Department of Mathematics,
University of California San Diego


Department Colloquium

Matija Bucić

Institute for Advanced Study

Robust sublinear expanders


Expander graphs are perhaps one of the most widely useful classes of graphs ever considered. In this talk, we will focus on a fairly weak notion of expanders called sublinear expanders, first introduced by Komlós and Szemerédi around 25 years ago. They have found many remarkable applications ever since. In particular, we will focus on certain robustness conditions one may impose on sublinear expanders and some applications of this very recent idea, which include: 

- recent progress on one of the most classical decomposition conjectures in combinatorics, the Erdős-Gallai Conjecture,

- Rainbow Turan problem for cycles, raised by Keevash, Mubayi, Sudakov and Verstraete, including an application of this result to additive number theory and 

- essentially tight answers to the classical Erdős unit distance and distinct distances problems in "almost all" real normed spaces of any fixed dimension.

Jacques Verstraete

February 23, 2023

4:00 PM

APM 6402