Id: arxiv/2607.09049 Url: https://arxiv.org/abs/2607.09049 Tags: math.CO Score: 0 Title: A Single-Exponential Erdős--Hajnal Bound for Graphs of Bounded VC-Dimension Domain: math.CO Source: arxiv Authors: Shuang Sun, Yan Wang, Jiasheng Zeng Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-10 Page: https://delphi.science/r/arxiv/2607.09049 A homogeneous set in a graph is a clique or a stable set. The Erdős--Hajnal conjecture states that, for every graph $H$, there exists $c>0$ such that every $H$-free graph on $n$ vertices has a homogeneous set of size at least $n^c$. Nguyen, Scott and Seymour proved that for every $d>0$, graphs of VC-dimension at most $d$ have the Erdős--Hajnal property, confirming a conjecture of Fox, Pach and Suk. In particular, they showed that every such $n$-vertex graph contains a homogeneous set of size at least $n^{η_d}$ for some $η_d\ge 2^{-2^{O(d)}}$. In this paper, we give a sharper quantitative…