Georgia Institute of Technology College of Sciences

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.