Asymptotic Erdős–Hajnal conjecture for forbidden order-size pairs
Asymptotic Erdős–Hajnal conjecture for forbidden order-size pairs
Let be an -vertex -graph, let denote the number of values of for which contains vertices spanning exactly edges, and let be the threshold function used in the source. A homogeneous set is a clique or an independent set. Asymptotic Erdős–Hajnal conjecture. Every -vertex -graph with no homogeneous sets of size satisfies
The preceding non-asymptotic conjecture is false, as a construction of J. Fox gives a counterexample for ; 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.