- Series
- Time
- Friday, November 15, 2024 - 3:15pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Dhruv Mubayi – University of Illinois at Chicago – mubayi@uic.edu – https://homepages.math.uic.edu/~mubayi/
- Organizer
- Xiaoyu He
Given integers $1 < s < t$, what is the maximum size of a $K_s$-free subgraph that every $n$ vertex $K_t$-free graph is guaranteed to contain? This problem was posed by Hajnal, Erdős and Rogers in the 1960s as a way to generalize classical graph Ramsey numbers (which corresponds to the case $s=2$). We prove almost optimal results in the case $t=s+1$ using recent constructions in Ramsey theory. We also consider the problem where we replace $K_s$ and $K_t$ by arbitrary graphs $H$ and $G$ and discover several interesting new phenomena. This is joint work with Jacques Verstraete.