{"id":"arxiv/2607.16118","url":"https://arxiv.org/abs/2607.16118","tags":["math.CO"],"score":0,"title":"On the Erdős-Rogers function","domain":"math.CO","source":"arxiv","authors":["Robert Morris","Julian Sahasrabudhe","Jacques Verstraëte"],"reviews":0,"subject":"math.CO","summary":"We show that the Erdős-Rogers function $f_{s,s+1}(n)$ satisfies $$f_{s,s+1}(n) = Θ( \\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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-17","reactions":{}}