On the Erdős-Rogers function

2026/07/17 by Robert Morris, Julian Sahasrabudhe, Jacques Verstraëte
Mathematics · #math.CO

paper · pdf

Abstract

We show that the Erdős-Rogers function f_s,s+1(n) satisfies f_s,s+1(n) = Θ( √(n log n) ) for every s ≥ 2. More precisely, we construct a K_s+1-free graph on n vertices in which every set of at least C(s)√(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.

Citations

• On a Problem of Formal Logic

Related

• On the order of Erdős-Rogers functions
• Hypergraph Erdős--Rogers functions with consecutive clique sizes
• Induced subgraphs of K_r-free graphs and the Erdős--Rogers problem
• Erdős-Rogers functions for arbitrary pairs of graphs
• Multicolor Erdős--Rogers Functions