On the Erdős-Rogers function

Abstract

We show that the Erdős-Rogers function $f_{s,s+1}(n)$ satisfies $$f_{s,s+1}(n)=\hat{I}˜(\sqrt{n\log n})$$ for every $s\ge 2$. More precisely, we construct a $K_{s+1}$-free graph on $n$ vertices in which every set of at least $C(s)\sqrt{n\log n}$ vertices contains a copy of $K_s$ for some constant $C(s)$, which implies the upper bound. The matching lower bound follows from a theorem of Joret, Micek, Reed and Smid on the clique chromatic number of a graph.

22 pages