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

From papers

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.

Progress summary

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

Sources & referencesView supporting material

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).

Solutions 0

No solutions have been posted yet.