Polynomial error term in H-free clique maximization
Informal Conjecture (error term in Proposition 1.4) · arXiv:1706.05642
Status open high confidence
Proposition 1.4 of Alon–Shikhelman (arXiv:1706.05642) asserts that for every graph $H$ with $\chi(H)=k$, any $H$-free subgraph of a sufficiently dense graph maximizing copies of $K_m(t)$ can be made $(k-1)$-colorable by deleting $o(n^2)$ edges; the authors conjecture that $o(n^2)$ can be sharpened to $O(n^{2-\delta})$ for some $\delta=\delta(H)>0$. No published or posted paper resolving or making partial progress on this specific conjecture was found in a broad web search covering 2017–2026.
Reviewer notes. No follow-up found addressing the conjectured improvement of the error term. The conjecture is a quantitative sharpening of Proposition 1.4 (which covers non-edge-critical $H$); Theorems 1.2–1.3 handle edge-critical $H$ with exact $(k-1)$-colorability. The $o(n^2)$ deletion bound is standard in graph removal / regularity arguments; improving it to $O(n^{2-\delta})$ would require new techniques (e.g. arithmetic or algebraic methods), which may explain the lack of progress.
Context
Proposition 1.4 shows that for every graph $H$ with $\chi(H) = k$ (not necessarily edge critical), any $H$-free subgraph of a sufficiently dense graph $G$ maximizing copies of $K_m(t)$ can be made $(k-1)$-colorable by deleting $o(n^2)$ edges. The authors note that Theorems 1.2 and 1.3 cannot be directly generalized to non-edge-critical $H$ since one can add an edge to any $(k-1)$-partite graph without creating a copy of such $H$, but they believe the $o(n^2)$ deletion bound in Proposition 1.4 is not tight.
Notes. Stated in the introduction as 'we believe'; Section 6 (concluding remarks and open problems) is not present in the extracted text and may contain additional items.
Source paper
$H$-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups
Noga Alon, Clara Shikhelman · 2017-06-18
https://arxiv.org/abs/1706.05642
PDF source