A Single-Exponential Erdős--Hajnal Bound for Graphs of Bounded VC-Dimension
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.09049
curl -X POST /api/v1/records/arxiv/2607.09049/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.09049/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'