Asymptotic Erdős–Hajnal conjecture for forbidden order-size pairs

Let GG be an nn-vertex rr-graph, let s(G;m)s(G;m) denote the number of values of ff for which GG contains mm vertices spanning exactly ff edges, and let gr(m)g_r(m) be the threshold function used in the source. A homogeneous set is a clique or an independent set. Asymptotic Erdős–Hajnal conjecture. Every nn-vertex rr-graph with no homogeneous sets of size nΩ(1)n^{\Omega(1)} satisfies

s(G;m)(1om(1))gr(m).s(G;m)\geq (1-o_m(1))g_r(m).

The preceding non-asymptotic conjecture is false, as a construction of J. Fox gives a counterexample for m=2rm=2r; this asymptotic formulation is proposed as a plausible replacement. Its general status is open.

Sources & referencesView supporting material

Primary source

Fabian Arnold, Lior Gishboliner and Benny Sudakov, “Two Erdos-Hajnal-type theorems for forbidden order-size pairs”, arXiv:2406.04154 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.