Talk information

Date: Sunday, January 19, 2025
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Lior Gishboliner (University of Toronto)
Title: New Erdős-Rogers-type results for arbitrary graphs

Abstract:

The generalized Erdős-Rogers problem asks, for given graphs $F,H$ and an integer $n$, for the maximum $m$ such that every $F$-free graph on $n$ vertices contains an $H$-free induced subgraph on $m$ vertices. The original Erdős-Rogers problem is when $F,H$ are cliques, and the case $H=K_2$ corresponds to off-diagonal Ramsey numbers. The study of the generalized problem was initiated recently by Mubayi and Verstraete, and we present solutions to some of their open problems. In particular, we show that for every $\epsilon > 0$ there is a large enough $d$ such that for every graph $H$ with average degree at least $d$, every $n$-vertex $K_4$-free graph contains an $H$-free induced subgraph of size at least $n^{1/2 - \epsilon}$.

This is a joint work with Oliver Janzer and Benny Sudakov.