On the Erdős-Rogers function

Robert Morris, Julian Sahasrabudhe, Jacques Verstraëte

We show that the Erdős-Rogers function $f_{s,s+1}(n)$ satisfies $$f_{s,s+1}(n)=\Theta (\sqrt{n\log n})$$ for every $s\ge 2$. More precisely, we construct a $K_{s+1}$-free graph on…