{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-10","reactions":{}}