betaFeedback

WorksMathematics

The Erdős–Hajnal property for paths

Abstract

The well-known Erdős-Hajnal conjecture states that for any graph HH, there is a constant c=c(H)>0c=c(H)>0 such that every nn-vertex graph GG with no induced copies of HH contains a clique or an independent set of size at least ncn^{c}. In this paper, we prove that the Erdős-Hajnal conjecture holds for every path.

Introduction

A clique (stable set) is a vertex set whose vertices are pairwise adjacent (nonadjacent, resp.). Ramsey [13] proved that for every integer k≥1k \ge1, there exists a positive integer R(k,k)R(k,k) such that every graph on at least R(k,k)R(k,k) vertices contains a clique or stable set of size kk. This shows that a sufficiently large graph must contain a large clique or stable set. Erdős [6] proved via the probabilistic method that for large nn, there exists an nn-vertex graph with no cliques or stable sets of size at least 2log⁡n2\log n. This shows that general graphs do not necessarily contain a clique or stable set of polynomial size. However, HH-free graphs might behave differently.

Let G,HG,H be graphs. We say that GG is HH-free if GG has no induced subgraph that is isomorphic to HH. In 1989, Erdős and Hajnal [7] showed that for any graph HH, there exists a constant c=c(H)>0c=c(H)>0 such that any nn-vertex HH-free graph has a clique or stable set of size at least eclog⁡ne^{c\sqrt{\log n}}. Erdős and Hajnal [7] further conjectured that one can improve the bound to a polynomial of nn, which has become known as the Erdős-Hajnal conjecture.

Conjecture 1. (Erdős-Hajnal [7]) For every graph HH, there exists c=c(H)>0c=c(H)>0 such that every nn-vertex HH-free graph has a clique or stable set of size at least ncn^c.

We say a graph HH has the Erdős-Hajnal property if HH satisfies Conjecture 1. The property is preserved under complementation and, by a theorem of Alon, Pach and Solymosi [1], under substitution. It holds for all graphs with at most four vertices, for the bull [4], for the five-cycle [5] and for the five-vertex path P5P_5 [12]. The last result completed the case of all five-vertex graphs. Huang, Ju and Zhou [9] developed the method of [12] into a general framework and used it for two six-vertex graphs. We refer to [3] for a survey.

Paths are a natural family to consider next. Nguyen, Scott and Seymour [11] proved that every PsP_s-free graph on nn vertices has a clique or stable set of size 2(log⁡n)1−o(1)2^{(\log n)^{1-o(1)}}. We prove the conjecture for all paths.

Theorem 1.1. For every integer s≥1s \ge1 there is τs>0\tau_s > 0 such that every PsP_s-free graph GG has a clique or a stable set of size at least ∣G∣τs|G|^{\tau_s}.

Independent work. The proof of Theorem 1.1, together with its Lean formalization, was made public on 7 October 2026 and archived on Zenodo on 9 October 2026 [16]. Later, on 17 October 2026, Nguyen [10] posted on arXiv an independent proof of the Erdős–Hajnal property for all paths, by a different method. As reported in [10], a team at Google Research and Google DeepMind has also announced an independent proof.

Preliminaries

Notation

All graphs are finite and simple. For a graph GG we write ∣G∣|G| for its number of vertices, G‾\overline{G} for its complement and G[S]G[S] for the subgraph induced on S⊆V(G)S \subseteq V(G). We write N(v)N(v) for the set of neighbors of vv in GG. PrP_r is the path with rr vertices. A class of graphs is hereditary if it is closed under taking induced subgraphs. A hereditary class C\mathcal{C} has the Erdős–Hajnal property if there is τ>0\tau> 0 such that every G∈CG \in\mathcal{C} has a clique or a stable set of size at least ∣G∣τ|G|^\tau. We call τ\tau an Erdős–Hajnal exponent of C\mathcal{C}, and for a graph HH we write EH⁡(H)\operatorname{EH}(H) for the statement that the class of HH-free graphs has this property. We write hom⁡(G)\operatorname{hom}(G) for the largest size of a clique or a stable set of GG and [k]={1,…,k}[k] = \{1, \ldots, k\} for an integer k≥1k \ge1.

Let A,B⊆V(G)A, B \subseteq V(G) be disjoint. AA is complete (anticomplete) to BB if every vertex of AA is adjacent (nonadjacent) to every vertex of BB. A vertex v∉Av \notin A is mixed on AA if it has a neighbor and a nonneighbor in AA. For x>0x > 0, BB is xx-sparse to AA if every vertex of BB has at most x∣A∣x|A| neighbors in AA, and (A,B)(A, B) is weakly xx-sparse if the number of edges between AA and BB is at most x∣A∣∣B∣x|A||B|. If BB is xx-sparse to AA, then (A,B)(A, B) is weakly xx-sparse.

GG is xx-sparse if its maximum degree is at most x∣G∣x|G|, and xx-restricted if GG or G‾\overline{G} is xx-sparse. A set S⊆V(G)S \subseteq V(G) is xx-sparse (xx-restricted) if G[S]G[S] is. A graph is anticonnected if its complement is connected, and the anticonnected components of GG are the subgraphs induced on the vertex sets of the components of G‾\overline{G}.

A blockade in GG is a sequence B=(B1,…,Bk)\mathcal{B} = (B_1, \ldots, B_k) of disjoint subsets of V(G)V(G). Its length is kk and its width is min⁡i∣Bi∣\min_i |B_i|. It is a (k,w)(k,w)-blockade if its length is at least kk and its width is at least ww. It is pure if every pair (Bi,Bj)(B_i, B_j) is complete or anticomplete, and complete (anticomplete) if every pair is complete (anticomplete). We write V(B)=⋃i=1kBiV(\mathcal{B}) = \bigcup_{i=1}^k B_i. We call a blockade B\mathcal{B}

  • xx-semisparse if for all i<ji < j, either BjB_j is complete to BiB_i, or BjB_j is xx-sparse to BiB_i;

  • weakly xx-semisparse if for all distinct i,ji,j the pair (Bi,Bj)(B_i, B_j) is complete or weakly xx-sparse.

Following [12, 9], an (ℓ,w)(\ell,w)-comb in GG is a sequence ((ai,Bi):i∈[ℓ])((a_i,B_i): i \in[\ell]) such that (B1,…,Bℓ)(B_1,\ldots,B_\ell) is an (ℓ,w)(\ell,w)-blockade, the vertices a1,…,aℓa_1,\ldots,a_\ell are distinct and do not belong to B1∪⋯∪BℓB_1 \cup\cdots\cup B_\ell, and for all distinct i,ji,j the apex aia_i is complete to BiB_i and anticomplete to BjB_j. A special vertex for the comb is a vertex vv outside the comb that is complete to B1∪⋯∪BℓB_1 \cup\cdots\cup B_\ell and anticomplete to {a1,…,aℓ}\{a_1,\ldots,a_\ell\}.

Results we use

The following results are used later.

Theorem 2.1 (Rödl [14]). For every graph HH and every ε∈(0,12)\varepsilon\in(0,\frac{1}{2}) there exists δ>0\delta> 0 such that every HH-free graph GG has an ε\varepsilon-restricted induced subgraph with at least δ∣G∣\delta|G| vertices.

Theorem 2.2 (Statement 3.1 of Nguyen–Scott–Seymour [11]). Let s≥2s \ge2 and 0<z≤1/(60s)0 < z \le1/(60s). Every z2z^2-sparse PsP_s-free graph GG with ∣G∣≥z−2|G| \ge z^{-2} has an anticomplete (1/z,⌊z2∣G∣⌋)(1/z,\lfloor z^2|G|\rfloor)-blockade.

(In [11] there is no lower bound on ∣G∣|G|, and then the blocks may be empty. We add the hypothesis ∣G∣≥z−2|G| \ge z^{-2}, which gives ⌊z2∣G∣⌋≥1\lfloor z^2|G|\rfloor\ge1, so that the blocks are nonempty. With this extra hypothesis the statement is a special case of the one in [11].)

Lemma 2.3 (Lemma 4.1 of Nguyen–Scott–Seymour [12]). Let k≥2k \ge2 be an integer, and let GG be a graph whose anticonnected components all have fewer than ∣G∣/k|G|/k vertices. Then GG has a complete (k,∣G∣/k2)(k,|G|/k^2)-blockade.

Lemma 2.4 (Lemma 2.10 of Huang–Ju–Zhou [9], contained in Lemma 5.2 of [12]). Let 0<x≤y≤2−80 < x \le y \le2^{-8}. For every y3y^3-sparse graph GG with ∣G∣≥y−4|G| \ge y^{-4}, one of the following holds:

  • there are disjoint X,Z⊆V(G)X,Z \subseteq V(G) with ∣X∣≥y4∣G∣|X| \ge y^4|G| and ∣Z∣≥(1−4y)∣G∣|Z| \ge(1-4y)|G| such that ZZ is xx-sparse to XX;

  • GG is 2y42y^4-*sparse; or

  • for some integer ℓ∈[y−1,x−2]\ell\in[y^{-1},x^{-2}] there is an (ℓ,y4∣G∣/ℓ2)(\ell,y^4|G|/\ell^2)-comb in GG with a special vertex.

The first two outcomes are directly useful for iterative sparsification. The comb is the main case, and in the proof of the local alternative for Ps‾\overline{P_s}-free graphs it is the only case that uses the forbidden graph. In [12, 9] the comb is turned into a pure blockade. For PsP_s we turn it into a weakly semisparse blockade or a restricted set in Lemma 6.2.

Theorem 2.5 (Alon–Pach–Solymosi [1], see also [9 Theorem 1.4]). If H1H_1 and H2H_2 have the Erdős–Hajnal property, then so does every graph obtained from H1H_1 by substituting H2H_2 for a vertex.

Theorem 2.6 (Chvátal [2]). Let GG be a graph with a linear order << of V(G)V(G) such that there is no induced path abcdabcd of GG with a<ba < b and d<cd < c. Then χ(G)=ω(G)\chi(G)=\omega(G). In particular GG has a clique or a stable set of size at least ∣G∣1/2|G|^{1/2}.

(The second statement follows from ∣G∣≤α(G)χ(G)=α(G)ω(G)|G| \le\alpha(G)\chi(G)=\alpha(G)\omega(G).) A graph with a linear order as in Theorem 2.6 is called perfectly orderable [2].

The reduction of Huang, Ju and Zhou

The last step of our proof is the reduction of Huang, Ju and Zhou [9], which refines the final part of [12]. We recall their definitions, specialised to a single forbidden graph and to a hereditary class.

References

  1. [1]N. Alon, J. Pach and J. Solymosi. Ramsey-type theorems with forbidden subgraphs. Combinatorica 21 (2001), 155–170.DOI
  2. [2]V. Chvá­tal. Perfectly ordered graphs. In Topics on Perfect Graphs, Annals of Discrete Mathematics 21 (1984), 63–65.DOI
  3. [3]M. Chudnovsky. The Erdős–Hajnal conjecture—a survey. J. Graph Theory 75 (2014), 178–190.
  4. [4]M. Chudnovsky and S. Safra. The Erdős–Hajnal conjecture for bull-free graphs. J. Combin. Theory Ser. B 98 (2008), 1301–1310.DOI
  5. [5]M. Chudnovsky, A. Scott, P. Seymour and S. Spirkl. Erdős–Hajnal for graphs with no 5-hole. Proc. Lond. Math. Soc. 126 (2023), 997–1014.arxiv.org/abs/2102.04994
  6. [6]P. Erdős. Some remarks on the theory of graphs. Bulletin of the American Mathematical Society, 53:292-294, 1947.DOI
  7. [7]P. Erdős and A. Hajnal. Ramsey-type theorems. Discrete Appl. Math. 25 (1989), 37–52.DOI
  8. [8]T. Gallai. Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hungar. 18 (1967), 25–66.DOI
  9. [9]S. Huang, Y. Ju and Y. Zhou. Erdős–Hajnal conjecture beyond five-vertex graphs. arXiv:2606.06258v3, 2026.
  10. [10]T. H. Nguyen. Erdős–Hajnal for excluding paths. arXiv:2610.24887, 2026.
  11. [11]T. Nguyen, A. Scott and P. Seymour. Induced subgraph density. V. All paths approach Erdős–Hajnal. arXiv:2307.15032, 2023.arxiv.org/abs/2307.15032
  12. [12]T. Nguyen, A. Scott and P. Seymour. Induced subgraph density. VII. The five-vertex path. Proc. Lond. Math. Soc. 132(3) (2026), e70133. arXiv:2312.15333.arxiv.org/abs/2312.15333
  13. [13]F. P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematical Society, 30:264-286, 1930.
  14. [14]V. Rödl. On universality of graphs with uniformly distributed edges. Discrete Math. 59 (1986), 125–134.DOI
  15. [15]V.-H. Tran and T. M. Nguyen. The Erdős–Hajnal property for the six-vertex graph with edge set {ab, bc, cd, de, af, bf, df}. arXiv:2608.28551, 2026.arxiv.org/abs/2608.28551
  16. [16]Y. Zhou. The Erdős–Hajnal property for paths. Zenodo, 9 October 2026, doi:10.5281/zenodo.23270286. Repository (public since 7 October 2026) with the Lean formalization: https://github.com/OctopusTide/erdos-hajnal-all-paths.

Paper details

vlnc:W_njwja8dw
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude Opus 5.5 (bare), ChatGPT-6

View statement
Looking for related papers…
Contents