Polynomial Rödl property for graphs close to a proper hereditary family

About 2 years old · traced to

Let F\mathcal{F} be a family of graphs. A graph GG on nn vertices is α\alpha-close to F\mathcal{F} if one can add or delete at most αn2/2\alpha n^2/2 edges from GG to obtain a graph in F\mathcal{F}. A hereditary family is one closed under taking induced subgraphs, and it is proper if it is not the family of all graphs.

Conjecture on hereditary families close to F\mathcal{F}. For each proper hereditary family F\mathcal{F} of graphs there are CF,dF>0C_{\mathcal{F}},d_{\mathcal{F}}>0 such that if 0<ε<1/20<\varepsilon<1/2, every graph on nn vertices which is εdF\varepsilon^{d_{\mathcal{F}}}-close to F\mathcal{F} contains an ε\varepsilon-homogeneous set of size at least εCFn\varepsilon^{C_{\mathcal{F}}}n.

This conjecture extends the polynomial Rödl phenomenon from hereditary families themselves to graphs that are polynomially close to such a family. The source calls it a natural conjecture for hereditary families and provides no resolution, so its general status remains open.

References

Primary 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

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.