An official website of the United States government
We prove the Erdős–Hajnal conjecture for the five-vertex path P5; that is, there exists c>0 such that every n-vertex graph with no induced P5 has a clique or stable set of size at least nc. This completes the verification of the Erdős–Hajnal conjecture for all five-vertex graphs. Our methods combine probabilistic and structural ideas with the iterative sparsification framework introduced in the third and fourth papers in the series.
more »
« less
This content will become publicly available on December 1, 2026
Induced subgraph density. VI. Bounded VC-dimension
We confirm a conjecture of Fox, Pach, and Suk, that for every d>0, there exists c>0 such that every n-vertex graph of VC-dimension at most d has a clique or stable set of size at least nc . 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.
more »
« less
- Award ID(s):
- 2154169
- PAR ID:
- 10688385
- Publisher / Repository:
- Elsevier
- Date Published:
- Journal Name:
- Advances in Mathematics
- Volume:
- 482
- Issue:
- PA
- ISSN:
- 0001-8708
- Page Range / eLocation ID:
- 110601
- Subject(s) / Keyword(s):
- VC-dimension Erdős-Hajnal conjecture Induced subgraphs
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
When H is a forest, the Gyárfás-Sumner conjecture implies that every graph G with no induced subgraph isomorphic to H and with bounded clique number has a stable set of linear size. We cannot prove that, but we prove that every such graph G has a stable set of size |G|1-0(1). If H is not a forest, there need not be such a stable set. Second, we prove that when H is a “multibroom”, there is a stable set of linear size. As a consequence, we deduce that all multibrooms satisfy a “fractional colouring” version of the Gyárfás-Sumner conjecture. Finally, we discuss extensions of our results to the multicolour setting.more » « less
-
We consider three graphs, 𝐺_{7,3}, 𝐺_{7,4}, and 𝐺_{7,6}, related to Keller’s conjecture in dimension 7. The conjecture is false for this dimension if and only if at least one of the graphs contains a clique of size 2^7 = 128. We present an automated method to solve this conjecture by encoding the existence of such a clique as a propositional formula. We apply satisfiability solving combined with symmetry-breaking techniques to determine that no such clique exists. This result implies that every unit cube tiling of ℝ^7 contains a facesharing pair of cubes. Since a faceshare-free unit cube tiling of ℝ^8 exists (which we also verify), this completely resolves Keller’s conjecture.more » « less
-
A $$k$$-kernel in a digraph $$G$$ is a stable set $$X$$ of vertices such that every vertex of $$G$$ can be joined from $$X$$ by a directed path of length at most $$k$$. We prove three results about $$k$$-kernels. First, it was conjectured by Erdős and Székely in 1976 that every digraph $$G$$ with no source has a 2-kernel $|K|$ with $$|K|\le |G|/2$$. We prove this conjecture when $$G$$ is a split digraph (that is, its vertex set can be partitioned into a tournament and a stable set), improving a result of Langlois et al., who proved that every split digraph $$G$$ with no source has a 2-kernel of size at most $2|G|/3$. Second, the Erdős-Székely conjecture implies that in every digraph $$G$$ there is a 2-kernel $$K$$ such that the union of $$K$$ and its out-neighbours has size at least $|G|/2$. We prove that this is true if $V(G)$ can be partitioned into a tournament and an acyclic set. Third, in a recent paper, Spiro asked whether, for all $$k\ge 3$$, every strongly-connected digraph $$G$$ has a $$k$$-kernel of size at most about $|G|/(k+1)$. This remains open, but we prove that there is one of size at most about $|G|/(k-1)$.more » « less
-
Abstract In 1977, Erd̋s and Hajnal made the conjecture that, for every graph $$H$$, there exists $c>0$ such that every $$H$$-free graph $$G$$ has a clique or stable set of size at least $$|G|^{c}$$, and they proved that this is true with $$ |G|^{c}$$ replaced by $$2^{c\sqrt{\log |G|}}$$. Until now, there has been no improvement on this result (for general $$H$$). We prove a strengthening: that for every graph $$H$$, there exists $c>0$ such that every $$H$$-free graph $$G$$ with $$|G|\ge 2$$ has a clique or stable set of size at least $$ \begin{align*} &2^{c\sqrt{\log |G|\log\log|G|}}.\end{align*} $$ Indeed, we prove the corresponding strengthening of a theorem of Fox and Sudakov, which in turn was a common strengthening of theorems of Rödl, Nikiforov, and the theorem of Erd̋s and Hajnal mentioned above.more » « less
