Polynomial bound for C₄-free average degree

Status open medium confidence

The question of whether a polynomial $p(k)$ suffices — so that average degree $\geq p(k)$ guarantees a $C_4$-free subgraph of average degree $\geq k$ — remains open. The known gap between the lower bound $k^{3-o(1)}$ and the upper bound $k^{Ck^2}$ (both from Montgomery, Pokrovskiy, and Sudakov) has not been closed as of this review. A June 2025 paper (arXiv:2506.23942) gives a related structural dichotomy for induced $C_4$-free subgraphs with geometric applications, but does not directly resolve the polynomial bound question.

Cited literature (1)

• partial $C_4$-free subgraphs of high degree with geometric applications (2025)
  not retrieved · arXiv preprint · arXiv:2506.23942

  Proves a structural dichotomy: every graph with average degree $d$ either contains an induced $C_4$-free subgraph with average degree at least $k$, or contains a $d$-vertex subgraph with $\Omega_k(d^2)$ edges; the paper applies this to obtain geometric results but does not resolve the polynomial bound question for $C_4$-free subgraphs.

Reviewer notes. The internal reference arXiv:2508.14332 is mismatched — verified by WebFetch to be entirely about the weak coarse Menger conjecture, unrelated to $C_4$-free subgraphs. arXiv:2506.23942 (June 2025) is the most relevant post-2023 paper found; it addresses induced $C_4$-free subgraphs via a dichotomy argument with geometric applications but does not directly answer whether a polynomial $p(k)$ suffices. Confidence is medium because this related June 2025 paper could contain implicit progress on the polynomial bound that requires reading the full text to assess.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).