VC-dimension and blowup threshold conjecture

From papers

Let $H$ be a graph. Let $\delta_{\textup{VC}}(H)$ be the infimum of those $\alpha$ such that every maximal $H$ -free graph $G$ with minimum degree at least $\alpha n$ has bounded VC-dimension, and let $\delta_{\textup{B}}(H)$ denote the blowup threshold.

VC-dimension–blowup threshold conjecture. For any graph $H$ ,

\delta_{\textup{VC}}(H)=\delta_{\textup{B}}(H).

The paper notes that $\delta_{\textup{VC}}(H)\leq\delta_{\textup{B}}(H)$ always, while equality is left open; for odd cycles, it is specifically open whether $\delta_{\textup{VC}}(C_{2k-1})=\frac{1}{2k-1}$ .

Progress summary

Open

The conjecture remains open: only one inequality is known, although the exact blowup threshold is known for odd cycles.

The conjecture asserts that, for every graph $H$ , the threshold forcing bounded VC-dimension in maximal $H$ -free graphs equals the blowup threshold. The available source records it as open and gives no proposer or date.

Known results

The general inequality $\delta_{\mathrm{VC}}(H)\leq\delta_{\mathrm{B}}(H)$ follows directly from the definitions.
For every $k\geq 2$ , $\delta_{\mathrm{B}}(C_{2k-1})=\frac{1}{2k-1}$ .
For odd cycles, sufficiently dense maximal $C_{2k-1}$ -free graphs have bounded VC-dimension, giving $\delta_{\mathrm{VC}}(C_{2k-1})\leq\frac{1}{2k-1}$ .
No reverse inequality, counterexample, or equality case is reported.

Current status (as of August 2026): The conjecture is open for general $H$ ; even whether $\delta_{\mathrm{VC}}(C_{2k-1})=\frac{1}{2k-1}$ remains unresolved.

Sources

arxiv.org

Sources & referencesView supporting material

Primary source

Xinqi Huang, Hong Liu, Mingyuan Rong and Zixiang Xu, “Interpolating chromatic and homomorphism thresholds”, arXiv:2502.09576 (2025).

1 week ago