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.

Date & Time

February 21, 2023 | 10:30am – 12:30pm


Simonyi Hall 101 and Remote Access


Veblen Research Instructor, School of Mathematics