Tutte Colloquium | Recent Progress on Erdos-Rogers Function

Abstract: For positive integers $s$ and $n$, let $f_{s}(n)$ denote the maximum $k$ such that every $n$-vertex $K_{s+1}$-free graph contains an induced $K_s$-free subgraph with $k$ vertices. These are the Erd\H{o}s-Rogers functions, introduced by Erd\H{o}s and Rogers in 1962, and are generalizations of Ramsey numbers. In this talk we survey recent progress, culminating with the recent result of Morris, Saharasbudhe which finally determines the order of magnitude of the Erd\H{o}s-Rogers functions.Joint work with Rob Morris and Julian Saharasbudhe.

Biography: Jacques Verstraete is currently a full professor in the Department of Mathematics at UC San Diego in La Jolla, California. He received his PhD from Cambridge University in the Department of Pure Mathematics and Mathematical Statistics - DPMMS - under the supervision of Professor Andrew Thomason, after completing Part III of the mathematical tripos. Professor Verstraete held academic, teaching, or research positions at the University of Washington, Seattle, Microsoft Research Redmond (Theory Group), University of Waterloo (Department of Combinatorics and Optimization), McGill University (Department of Mathematics). Professor Verstraete undertook recent sabbaticals at IPAM (UCLA), (and UCLA Lake Arrowhead conference center), the Mittag-Leffler Institute (Stockholm), ETH (Zurich), and the Simons-Laufner Institute (Berkeley).