Computer Science/Discrete Mathematics Seminar II

Expander graphs have been 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 Komlos and Szemeredi 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 while still maintaining their most useful property, the fact that in any graph one can find a sublinear expander subgraph of almost the same density. We will discuss a number of useful properties of such robust sublinear expanders and show how they come together to bring us only a $\log^{\star}$ factor away from proving one of the most classical decomposition conjectures, the Erdos-Gallai cycle decomposition conjecture.

Based on joint work with Richard Montgomery.