Induced subgraph density. VI. Bounded VC-dimension

Journal article

We confirm a conjecture of Fox, Pach, and Suk, that for every , there exists  such that every -vertex graph of VC-dimension at most  has a clique or stable set of size at least . This implies that, in the language of model theory, every graph definable in NIP structures has a clique or anti-clique of polynomial size, settling a conjecture of Chernikov, Starchenko, and Thomas. Our result also implies that every two-colourable tournament satisfies the tournament version of the Erdős-Hajnal conjecture, which completes the verification of the conjecture for six-vertex tournaments. The result extends to uniform hypergraphs of bounded VC-dimension as well. The proof method uses the ultra-strong regularity lemma for graphs of bounded VC-dimension proved by Lovász and Szegedy and the method of iterative sparsification introduced by the authors in an earlier paper.

Authors: Nguyen, T; Scott, AD; Seymour, P

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Advances in Mathematics
• Volume: 482
• Issue: Part A
• Article number: 110601
• Publication date: 2025-10-14
• Acceptance date: 2025-09-24
• DOI: 10.1016/j.aim.2025.110601
• EISSN: 1090-2082
• ISSN: 0001-8708
• Language: English
• Keywords: induced subgraphs; Erdős-Hajnal conjecture; VC-dimension