Density separation conjecture for polynomial Ramsey classes

For a family F\mathcal{F} of 33-graphs, define

e(F)=lim supHFe(H)(v(H)3).e(\mathcal{F})=\limsup_{H\in\mathcal{F}}\frac{e(H)}{\binom{v(H)}{3}}.

Let Fpoly\mathcal{F}_{\mathrm{poly}}, Fpart-poly\mathcal{F}_{\mathrm{part\text{-}poly}}, Fpolyfact\mathcal{F}_{\mathrm{polyfact}}, and Fpart-polyfact\mathcal{F}_{\mathrm{part\text{-}polyfact}} be the graph families defined in the paper. Density separation conjecture.

e(Fpoly)<e(Fpart-poly)ande(Fpolyfact)<e(Fpart-polyfact).e(\mathcal{F}_{\mathrm{poly}})<e(\mathcal{F}_{\mathrm{part\text{-}poly}})\quad\text{and}\quad e(\mathcal{F}_{\mathrm{polyfact}})<e(\mathcal{F}_{\mathrm{part\text{-}polyfact}}).

This conjecture predicts that allowing the relevant multipartite constructions strictly enlarges the attainable edge-density limits. The excerpt presents both inequalities as unresolved quantitative questions.

Sources & referencesView supporting material

Primary source

Jacob Fox and Xiaoyu He, “Independent sets in hypergraphs with a forbidden link”, arXiv:1909.05988 (2021).

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.