Erdős Problem 1092

References:

• Erdős Problem 1092
• [Ro82] V. Rödl, On the chromatic number of subgraphs of a given graph, Proc. Amer. Math. Soc. 85 (1982), 382–386

noncomputable def Erdos1092.f (r m : ℕ) : ℕ

Let $f_r(m)$ be maximal such that, if any graph $G$ has the property that every subgraph $H$ on $m$ vertices is the union of a graph with chromatic number $\leq r$ and a graph with $\leq f_r(m)$ edges, then $G$ has chromatic number $\leq r+1$.

The quantification is over all finite graphs $G$ (of any size), not just graphs on a fixed vertex set.

Equations

• One or more equations did not get rendered due to their size.

theorem Erdos1092.f_asymptotic_2 : False ↔ (fun (n : ℕ) => ↑n) =o[Filter.atTop] fun (n : ℕ) => ↑(f 2 n)

Is it true that $f_2(n) \gg n$? Disproved by Rödl, who showed $f_r(n) = o(n)$ for all fixed $r \geq 2$. A conjecture of Erdős, Hajnal, and Szemerédi.

This seems to be closely related to, but distinct from, 744.

Tang notes in the comments that Rödl [Ro82] constructed, for any $\epsilon>0$ and $k$, a graph with chromatic number $\geq k$ such that every graph on $m$ vertices is bipartite after deleting at most $\epsilon m$ edges.

theorem Erdos1092.f_asymptotic_general : False ↔ ∀ (r : ℕ), (fun (n : ℕ) => ↑r * ↑n) =o[Filter.atTop] fun (n : ℕ) => ↑(f r n)

More generally, is $f_r(n)\gg_r n$? Disproved by Rödl, who showed $f_r(n) = o(n)$ for all fixed $r \geq 2$.