Computer Science/Discrete Mathematics Seminar II
From Robust Sublinear Expanders to Additive Number Theory via Rainbow Cycles
Robust sublinear expansion represents a fairly weak notion of graph expansion which still retains a number of useful properties of the classical notion. The general idea behind it has been introduced by Komlós and Szemerédi around 25 years ago and has since been significantly developed, resulting in a number of remarkable applications over the years. I will briefly mention a number of very recent ones including:
- progress towards the classical Erdős-Gallai cycle decomposition conjecture
- an essentially tight answer to the classical Erdős unit distance and distinct distance problems for "almost all" finite-dimensional real normed spaces and
- an essentially tight answer to the rainbow Turan problem for cycles, raised by Keevash, Mubayi, Sudakov and Verstraete.
The main part of the talk will focus on the rainbow Turan problem for cycles and how it connects to several other topics including a couple from additive number theory, namely a notion of additive dimension and a variant of the Davenport constant.
Based on joint works with Montgomery; Alon and Sauermann; and Alon, Sauermann, Zakharov and Zamir.