Fox–Sudakov polynomial Rödl conjecture
Let be a graph. For a graph , a vertex set is -homogeneous if the edge density of the induced graph is at most or at least .
Fox–Sudakov's conjecture. For any graph there exists a such that for any any -vertex -free graph contains an -homogeneous set with at least vertices.
This is a polynomial quantitative strengthening of Rödl's theorem and implies the Erdős–Hajnal conjecture for each fixed graph . The source presents it as an open conjecture, while the paper proves equivalence with the Erdős–Hajnal and polynomial Nikiforov conjectures.
References
2 papers in this index state this conjecture (2023–2024). The statement above is taken from the most recent of them; the others are arXiv:2307.06455.
Source: Matija Bucić, Jacob Fox and Huy Tuan Pham, “Equivalence between Erdős-Hajnal and polynomial Rödl and Nikiforov conjectures”, arXiv:2403.08303 (2024).
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
No solutions have been posted yet.