Erdős–Hajnal conjecture: forbidding one induced subgraph forces polynomial-size cliques/independent sets

Statement

The Erdős–Hajnal conjecture (posed by Erdős and Hajnal in 1977; published P. Erdős, A. Hajnal, "Ramsey-type theorems," *Discrete Applied Mathematics* 25 (1989), 37–52): for every graph $H$ there is a constant $\delta(H)>0$ such that every $n$-vertex graph $G$ with no induced subgraph isomorphic to $H$ (i.e. $G$ is "$H$-free" in the induced sense) contains a clique or an independent (stable) set of size at least $n^{\delta(H)}$.

Why this is surprising / the contrast it is stated against. For a *general* $n$-vertex graph with no forbidden pattern at all, Ramsey's theorem only guarantees a monochromatic clique-or-independent-set of size $\Theta(\log n)$, and this is tight: Erdős's 1947 random-graph argument shows $G_{n,1/2}$ has $\omega,\alpha=(2+o(1))\log_2 n$ whp (see Ramsey-type concentration of the independence/clique number of G(n,1/2)). The Erdős–Hajnal conjecture says that merely forbidding one fixed graph as an induced subgraph — an extremely weak structural restriction, since $H$ can still appear as a non-induced subgraph — is enough to force this logarithmic bound up to polynomial in $n$, i.e. an exponentially larger guarantee, with the exponent $\delta(H)$ depending only on $H$, not on $n$ or $G$. (en.wikipedia.org/wiki/Erdős–Hajnal_conjecture; openproblemgarden.org/op/the_erdos_hajnal_conjecture)

Status: open in general, but with a substantial and actively growing body of proved special cases (below) and a proved universal *sub-polynomial* baseline that holds unconditionally for every $H$.

Universal unconditional baseline (Erdős–Hajnal 1989). For every graph $H$ there is $c(H)>0$ such that every $H$-free $n$-vertex graph has a clique or independent set of size at least $\exp\!\big(c(H)\sqrt{\log n}\big)$ — strictly super-logarithmic (beating the generic $\Theta(\log n)$ Ramsey bound for *every* fixed $H$, unconditionally), but strictly sub-polynomial, leaving the gap up to $n^{\delta(H)}$ as exactly the content of the conjecture.

**Tournament analogue (Berger, Choromański, Chudnovsky, Fox, Loebl, Scott, Seymour, Thomassé, "Tournaments and colouring," *J. Combin. Theory Ser. B* 103 (2013) 1–20). Replace "induced $H$-free graph" with "induced-$T$-free tournament" and "clique or independent set" with "transitive sub-tournament"; this tournament-level Erdős–Hajnal conjecture is proved equivalent** to the graph-level one, and is often technically easier to attack because tournaments compose more cleanly under substitution.

Hypergraph analogue (the literal clique-or-independent-set generalization is FALSE for $k\ge4$; a weakened complete/empty-blow-up version is the correct analogue, proved for $k=3$). See Facts/Technique below and Conlon–Fox–Sudakov (2011/2012) — the Erdős–Hajnal conjecture has a tripartite 3-uniform analogue, and provably NO clique/independent-set analogue for k>3 for the full statement.

Facts

- Origin and naming. Posed by P. Erdős and A. Hajnal in 1977, published in P. Erdős, A. Hajnal, "Ramsey-type theorems," *Discrete Applied Mathematics* 25 (1989), 37–52. (en.wikipedia.org/wiki/Erdős–Hajnal_conjecture) - Proved for all graphs on ≤4 vertices, and — as of Nguyen–Scott–Seymour 2023/2026 (below) — for all graphs on 5 vertices, closing what had been an actively studied gap. (en.wikipedia.org/wiki/Erdős–Hajnal_conjecture; multiple corroborating sources below) - Cographs / $P_4$-free graphs: proved directly by Erdős and Hajnal themselves, via the fact that $P_4$-free graphs are exactly those built up from single vertices by disjoint union and join (complementation) — their modular decomposition is trivial, giving $\delta=1$ essentially by structural induction. (Seinsche 1974, "On a property of the class of $n$-colorable graphs," *JCTB* 16, cited in the Chudnovsky survey as the structural fact underlying this.) - Bull-free graphs (the "bull" = triangle with two disjoint pendant edges): M. Chudnovsky, S. Safra, "The Erdős–Hajnal conjecture for bull-free graphs," *JCTB* 98 (2008), 1301–1310. - $(P_5,\overline{P_5})$-free graphs: J.L. Fouquet, "A decomposition for a class of $(P_5,\overline{P_5})$-free graphs," *Discrete Mathematics* 121 (1993), 75–83 — an early partial result on the smallest genuinely hard case, later strengthened. - $C_5$ (five-hole)-free graphs — resolved 2021/2023. M. Chudnovsky, A. Scott, P. Seymour, S. Spirkl, "Erdős–Hajnal for graphs with no 5-hole," *Combinatorica*/*Proc. London Math. Soc.* (2023), arXiv:2102.04994 — proves the conjecture true when $H=C_5$, a case explicitly posed as open by Lovász and unresolved for decades; the paper also proves a joint strengthening for $\{C,\overline{F}\}$-free graphs where $C$ is any cycle and $F$ any forest. Note: several older secondary sources (e.g. openproblemgarden.org, as fetched this session) still list $C_5$ as open — that listing is now outdated. - $P_5$ (five-vertex path)-free graphs — resolved 2023/2026, was "the smallest open case." P. Blanco, M. Bucić, "Towards the Erdős–Hajnal conjecture for $P_5$-free graphs," arXiv:2210.10755 (2022), first improved the universal $2^{\Omega(\sqrt{\log n})}$ Erdős–Hajnal-1989 bound to $2^{\Omega((\log n)^{2/3})}$ specifically for $P_5$-free graphs (still sub-polynomial). This was then fully resolved by T. Nguyen, A. Scott, P. Seymour, "Induced subgraph density VII: the five-vertex path," arXiv:2312.15333, published *Proc. London Math. Soc.* 132(3):e70133 (2026): genuine polynomial bound $n^{c}$ for some $c>0$, using "probabilistic and structural ideas with the iterative sparsification framework" developed across their "Induced subgraph density" paper series. Follow-up work extends the same framework to slightly larger graphs built from $P_5$/the bull: "Erdős–Hajnal beyond the five-vertex path," arXiv:2606.06258 (2026). - Substitution/modular-composition closure (Alon–Pach–Solymosi 2001). N. Alon, J. Pach, J. Solymosi, "Ramsey-type theorems with forbidden subgraphs," *Combinatorica* 21 (2001), 155–170: if graphs (or graph families) $F, H_1,\dots,H_n$ each individually satisfy the Erdős–Hajnal property, then the graph obtained by "substituting" $H_i$ for the $i$-th vertex of $F$ (i.e. blowing up each vertex of $F$ into a copy of $H_i$ and joining/not-joining according to $F$'s adjacency) also satisfies the property. This is the single most-reused tool for building new proved cases from old ones — see Technique. - Random / almost-all graphs already satisfy it. M. Loebl, B. Reed, A. Scott, S. Thomassé, A. Thomason, "Almost all $H$-free graphs have the Erdős–Hajnal property," *An Irregular Mind (Szemerédi is 70)*, Bolyai Soc. Math. Studies 21 (2010), 405–414 — the conjecture's difficulty is concentrated on a small set of "adversarial" $H$-free graphs, not typical ones. - VC-dimension special case — proved unconditionally for ALL $H$ within bounded-VC-dimension graph families. J. Fox, J. Pach, A. Suk (and related authors), "Erdős–Hajnal Conjecture for Graphs with Bounded VC-Dimension," SoCG 2017 / *Discrete Comput. Geom.* (2019): for every graph $H$ and every $d$, there is $f(d)>0$ such that every $H$-free graph with VC-dimension $\le d$ (as a set system on its vertex set defined by neighborhoods) has a clique or independent set of size $n^{f(d)}$ — proved via a purpose-built "ultra-strong regularity lemma" for bounded-VC-dimension (hyper)graphs. This matters because many geometrically/algebraically defined graph classes (intersection graphs of "nice" shapes, semialgebraic graphs) automatically have bounded VC-dimension, so EH is unconditionally known there regardless of which specific $H$ is forbidden. - Equivalence to polynomial strengthenings of Rödl's and Nikiforov's theorems (2024). J. Fox, T. Nguyen(?), A. Scott, P. Seymour et al., "Equivalence between Erdős-Hajnal and polynomial Rödl and Nikiforov conjectures," arXiv:2403.08303 (2024): shows the Erdős–Hajnal conjecture is logically equivalent to (a) a polynomial-quantitative strengthening of Rödl's classical theorem (every non-universal — i.e. $H$-free-for-some-$H$ — graph has a large "almost-homogeneous" induced subgraph of density near 0 or 1) and (b) a polynomial strengthening of a related theorem of Nikiforov, and further equivalent to analogous statements for tournaments, ordered graphs, and colored/hypergraph variants. This gives solvers multiple logically-interchangeable reformulations to attack (flagged lower confidence: abstract-level only, precise formal statements of the Rödl/Nikiforov sides not independently re-verified this session). - Hypergraph analogue exists, is provably FALSE in the literal form for $k\ge4$, and TRUE in a weakened (complete/empty tripartite blow-up) form for $k=3$. D. Conlon, J. Fox, B. Sudakov, "Erdős-Hajnal-type theorems in hypergraphs," arXiv:1104.5544, *JCTB* 102 (2012), 1142–1154 (full primary-source detail already in this wiki: see Conlon–Fox–Sudakov (2011/2012) — the Erdős–Hajnal conjecture has a tripartite 3-uniform analogue, and provably NO clique/independent-set analogue for k>3): (i) positive, $k=3$: every $H$-free 3-uniform hypergraph on $n$ vertices contains a complete-or-empty tripartite subgraph with parts of size $(\log n)^{1/2+\delta(H)}$, beating the universal unconditional $(\log n)^{1/2}$ bound that holds in *every* 3-uniform hypergraph (this is the correct hypergraph-shaped analogue of the graph EH conjecture, answering a question of Rödl and Schacht); (ii) negative, $k\ge4$: the *direct* clique-or-independent-set generalization of Erdős–Hajnal is impossible for $k$-uniform hypergraphs with $k\ge4$ — there exist $H$-free $k$-uniform hypergraph families whose largest homogeneous set is no bigger than the generic (unrestricted) hypergraph-Ramsey bound, via the Erdős–Hajnal *stepping-up* construction (a different, older piece of Erdős–Hajnal work — see concept/stepping-up-lemma) shown to be automatically $H$-free for a suitable $H$ by a pure counting/descriptive-complexity argument. The general $k$-partite blow-up rate for $k\ge4$ (conjectured $c(\log n)^{1/(k-2)}$) is open (Conjecture 1 of that paper).

Technique

When it applies. Whenever a problem reduces to: "$G$ is a graph (or tournament, or hypergraph) on $n$ objects that is known to avoid some fixed small induced pattern $H$ — how large a clique/independent-set/transitive-set/blow-up must it contain?" This is exactly the setting of hereditary graph classes (any class closed under induced subgraphs is, by the Erdős–Hajnal-Chvátal 1985-conjecture-adjacent taxonomy, definable by a — possibly infinite — set of forbidden induced subgraphs), so EH-style reasoning is the default first move whenever "induced-$H$-free" appears as a hypothesis.

Why it works (the mechanism, two layers).

1. The universal sub-polynomial baseline, mechanism. Erdős–Hajnal's 1989 exp$(c\sqrt{\log n})$ bound is obtained in two steps: (a) show every $H$-free graph on $N$ vertices contains a large induced perfect subgraph, of size $2^{c\sqrt{\log N}}$ — proved by repeatedly applying Ramsey's theorem/H-freeness together to peel off structure (each round either directly finds a big homogeneous set or forces enough local structure, via $H$-freeness, to make progress toward perfection); (b) invoke the classical fact that every perfect graph on $m$ vertices has $\omega(G)\cdot\alpha(G)\ge m$ (an easy consequence of the weak perfect graph theorem: $\chi(G)=\omega(G)$ and $\chi(G)\ge m/\alpha(G)$), hence a clique or independent set of size $\ge\sqrt m$. Composing (a) and (b) gives a clique-or-independent-set of size $\ge\sqrt{2^{c\sqrt{\log N}}}=2^{(c/2)\sqrt{\log N}}$. This "reduce to perfect, then use $\omega\alpha\ge n$" two-step is the reusable engine behind the *unconditional* part of the theory, and is the natural fallback whenever the sharper polynomial bound is out of reach for a specific $H$. 2. Substitution/modular decomposition, mechanism (why it builds new proved cases for free). If $F$ satisfies EH with exponent $\delta(F)$ and each $H_i$ satisfies EH with exponent $\delta(H_i)$, then in the substituted graph $F[H_1,\dots,H_n]$, any clique or independent set either lies almost entirely within one substituted copy $H_i$ (recurse: use $H_i$'s own EH property) or corresponds to a clique/independent set in the "outer" graph $F$ selecting one vertex from several copies (recurse: use $F$'s EH property on the outer structure) — the two recursive guarantees combine multiplicatively into a single polynomial exponent for the whole composite graph. Because modular decomposition (the canonical way of writing *any* graph as iterated substitution over prime/indecomposable pieces) is completely general, this lets solved cases (single vertices, cographs, bull, $C_5$, $P_5$, …) be freely recombined into much larger families of graphs $H$ for which EH($H$) is now automatically known, without any new proof — this is the single highest-leverage recombination move in this area. 3. Tournament reduction, mechanism. Converting a graph-level EH question into the equivalent tournament-level one (Berger–Choromański–Chudnovsky–Fox–Loebl–Scott–Seymour–Thomassé) is useful because "transitive sub-tournament" composes even more cleanly under substitution than "clique or independent set" does (a tournament substituted into a transitive tournament stays closer to transitive), and because tournament Ramsey-type arguments can borrow directed-graph-specific tools (e.g. the directed/oriented Szemerédi regularity lemma) that have no direct graph-level analogue. 4. VC-dimension route, mechanism. When the graph class in question arises from a *geometric or algebraic* definition (points/regions in $\mathbb{R}^d$, semialgebraic relations, etc.), it typically has bounded VC-dimension as a neighborhood set system; the ultra-strong regularity lemma for bounded-VC-dimension (hyper)graphs then gives EH unconditionally for every $H$ simultaneously in that class, sidestepping the need to prove EH($H$) case-by-case. This is the standard move whenever the "graph" in a problem is secretly a geometric intersection/incidence structure. 5. Recombination pattern for open problems. (a) Check whether the target $H$ decomposes (via modular decomposition) into pieces that are unions/substitutions of already-solved small graphs (single vertices, cographs, bull, $C_5$, $P_5$, and now — via arXiv:2606.06258 — small $P_5$/bull extensions) — if so, Alon–Pach–Solymosi gives EH($H$) immediately. (b) If not, check whether the ambient graph class has bounded VC-dimension (geometric/algebraic origin) — if so, EH is free regardless of $H$. (c) If neither applies, fall back to the universal exp$(c\sqrt{\log n})$ baseline via the perfect-graph route, and look for problem-specific structural refinements (iterative sparsification à la Nguyen–Scott–Seymour) to push toward polynomial. (d) If the setting is a $k$-uniform hypergraph rather than a graph, first check $k=3$: only the *tripartite-blow-up* form of EH is available (Conlon–Fox–Sudakov), not the literal clique/independent-set form; for $k\ge4$, the literal clique/independent-set form is provably false — do not attempt to prove it, redirect to the $k$-partite blow-up formulation instead (open in general for $k\ge4$).

What it does NOT give. No general algorithm or explicit value for $\delta(H)$ even in cases where existence of *some* $\delta(H)>0$ is proved (most positive results are qualitative/asymptotic, not sharp-constant). It does not resolve the conjecture for $H$ outside the union of (proved small cases) $\cup$ (substitution closure of those) $\cup$ (bounded-VC-dimension classes) — in particular $P_6$, most 6+-vertex graphs, and essentially all "generic" larger $H$ remain open. For hypergraphs, it gives no clique-or-independent-set-style guarantee at all once $k\ge4$ — that formulation is a dead end, proved impossible, not merely unproved.

Related

- Conlon–Fox–Sudakov (2011/2012) — the Erdős–Hajnal conjecture has a tripartite 3-uniform analogue, and provably NO clique/independent-set analogue for k>3 — the Conlon–Fox–Sudakov (2011/2012) hypergraph analogue in full primary-source detail: the $k=3$ tripartite-blow-up positive result and the $k\ge4$ impossibility result summarized in Facts/Technique above. - Ramsey-type concentration of the independence/clique number of G(n,1/2) — the contrasting *unconstrained* baseline ($\omega,\alpha=\Theta(\log n)$ for general/random graphs) that makes the polynomial jump under $H$-freeness surprising in the first place; also the source of the "clique-or-independent-set of size $n$ = Ramsey number" framing this conjecture generalizes. - Dependent random choice — pick a small random test-tuple, take its common neighborhood; the resulting set is large and almost every small subset of it still has a large common neighborhood, giving a workhorse for embedding sparse/bipartite graphs into dense hosts — the Fox–Sudakov technique family (Fox–Sudakov 2009, "Density theorems for bipartite graphs and related Ramsey-type results," a direct EH-adjacent paper) used for several bipartite/density-theorem partial results feeding into the polynomial-Rödl equivalence. - Hypergraph regularity / Gowers uniformity norms and density-increment arguments: quasirandom decomposition + counting/removal lemmas, and the iterative-density-increase route to Szemerédi-type theorems — the broader quasirandomness/regularity framework that Conlon–Fox–Sudakov's tri-$(\epsilon,\rho)$-density notion (used in the hypergraph analogue) specializes. - concept/stepping-up-lemma — the Erdős–Hajnal binary-string tower-type construction reused (in a completely different role, as the *impossibility* witness) to show no hypergraph analogue exists for $k\ge4$. - Kővári–Sós–Turán theorem: the double-counting bound ex(n,K_{s,t}) = O(n^{2-1/s}) — the Kővári–Sós–Turán double-counting engine that Conlon–Fox–Sudakov's tripartite blow-up proof (Lemmas 3.1–3.3) is built from, one layer beneath the hypergraph EH machinery.