Polynomial clique/independent set in bounded VC-dimension graphs

Conjecture 4.1 · arXiv:1912.02342

arXiv Conjecture high confidence— first stated 2019-12-05

Authors: Jacob Fox, Janos Pach, Andrew Suk

Status solved high confidence

Conjecture 4.1 from arXiv:1912.02342 has been fully resolved. Nguyen, Scott, and Seymour (arXiv:2312.15572, 2023) proved that for every d > 0, every n-vertex graph of VC-dimension at most d contains a clique or stable set of size at least n^c for an explicit constant c > 0 depending only on d, with the bound c_d ≥ 2^{-2^{O(d)}}. The proof also settles a related conjecture of Chernikov, Starchenko, and Thomas on graphs definable in NIP structures.

Cited literature (1)

proof Induced subgraph density. VI. Bounded VC-dimension (2023)

Tung Nguyen, Alex Scott, Paul Seymour · arXiv preprint · arXiv:2312.15572

Proves the conjecture in full: for every d > 0 there exists c > 0 such that every n-vertex graph of VC-dimension at most d contains a clique or stable set of size at least n^c, with explicit bound c_d ≥ 2^{-2^{O(d)}}.

Reviewer notes. The conjecture is solved by arXiv:2312.15572 (Nguyen, Scott, Seymour, submitted December 2023, revised September 2025). The internal reference entry for this paper was verified by WebFetch and confirms the proof matches Conjecture 4.1 exactly. The two internal reference entries for arXiv:2403.08303 concern a related but distinct set of equivalences among Erdős–Hajnal and polynomial Rödl/Nikiforov conjectures and do not directly resolve Conjecture 4.1.

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

Conjecture. For $d \geq 2$, there exists a constant $\varepsilon(d)$ such that every graph on $n$ vertices with VC-dimension at most $d$ contains a clique or an independent set of size $n^{\varepsilon(d)}$.

Context

This is the VC-dimension specialisation of the Erdős-Hajnal conjecture proposed by the paper's authors. The best known bound for graphs of bounded VC-dimension is $e^{(\log n)^{1-o(1)}}$, established in a companion paper by the same authors; Conjecture 4.1 asks for the much stronger polynomial bound.

Source paper

Bounded VC-dimension implies the Schur-Erdos conjecture
Jacob Fox, Janos Pach, Andrew Suk · 2019-12-05
https://arxiv.org/abs/1912.02342 PDF source