The blowup monotonicity conjecture of Korándi, Roberts and Scott

From papers

Fix k2k\geq 2, and let δ\delta be small enough. For any δ>δ0>0\delta>\delta_0>0 and sufficiently large nn, consider every C2k1C_{2k-1}-free graph GG on nn vertices satisfying

(14δ0)n2e(G)(14δ)n2.\left(\frac14-\delta_0\right)n^2\geq e(G)\geq\left(\frac14-\delta\right)n^2.

Korándi–Roberts–Scott's conjecture. There is a C2k+1C_{2k+1}-blowup GG^* satisfying

e(G)e(G)andγ2(G)γ2(G).e(G^*)\geq e(G)\qquad\text{and}\qquad\gamma_2(G^*)\geq\gamma_2(G).

The conjecture predicts that, in this dense near-bipartite range, an appropriate blowup preserves or improves both the edge count and the parameter γ2\gamma_2; the supplied source gives no resolution status.

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

Rui Wang and Shipeng Wang, “Longest odd cycles in non-bipartite C_2k+1-free graphs”, arXiv:2508.16199 (2025).

Solutions 0

No solutions have been posted yet.