Erdős–Hajnal Conjecture

The Erdös-Hajnal Conjecture

Definitions and mathematical statement

An induced copy of $H$ in $G$ is a vertex subset whose inherited edges and nonedges agree with $H$. A clique has all pairwise edges, and an independent set has none. The conjecture is \[ \forall H\ \exists c_H>0\ \forall G\text{ with no induced }H:\qquad \max(\omega(G),\alpha(G))\ge |V(G)|^{c_H}. \] The exponent may depend on the forbidden graph but not on the size of $G$. Excluding ordinary subgraphs or minors is not the same hypothesis.

Formulation and concept references: [S1].

Short English statement

Does forbidding any fixed induced graph force a polynomially large clique or independent set?

Research attempt

Current frontier.

Bucić--Fox--Pham prove the equivalence of the Erdős--Hajnal, polynomial Rödl, and polynomial Nikiforov properties; the easy sparsification-to-homogeneous-set direction is particularly useful here. [E1], Conjecture 2 and Theorem 7. The August 2026 revision of Huang--Ju--Zhou records the resolution for all graphs on at most five vertices and develops additional six-vertex cases. Its statements do not cover every forbidden finite graph. [E2], introduction. The present route uses induced-subgraph exclusion throughout; replacing it with an ordinary subgraph or minor condition would change the problem.

Attack routes.

An iterative density argument could succeed with polynomial loss in the accuracy parameter; ordinary qualitative regularity is not enough. A recursive decomposition into two large complete or anticomplete pieces looks stronger and potentially simpler, but it is false even for a very easy forbidden graph. A minimal-counterexample argument would therefore need weaker, quantitatively controlled sparsification, not pure pairs of fixed linear size. We prove the quantitative implication and construct an explicit probabilistic obstruction to the stronger recursive lemma.

Attempt I: exact exponent from polynomial sparsification.

Fix $H$. Suppose there is $a=a_H>0$ such that, for every $0<\varepsilon<1/2$ and every induced-$H$-free graph on $n$ vertices, there exists $U$ with \begin{equation}\label{wsref-0-33-32-38-31-3a-72-6f-64-6c} |U|\geq\varepsilon^a n,\qquad d(G[U])\leq\varepsilon\quad\text{or}\quad d(G[U])\geq1-\varepsilon. \end{equation} Density means the fraction of the $\binom{|U|}{2}$ possible edges; sets with fewer than two vertices can be treated separately. This is the polynomial Rödl condition of [E1], not a hypothesis proved here for every $H$.

For a graph on $m$ vertices with average degree at most $\varepsilon m$, there is an independent set of size at least \begin{equation}\label{wsref-0-33-32-38-31-3a-63-61-72-6f} \sum_{v}\frac1{\deg(v)+1}\geq\frac{m}{\varepsilon m+1}. \end{equation} Indeed, order the vertices uniformly at random and select each vertex that occurs before all of its neighbors. The selected vertices are independent, and the expected count is the displayed sum. The second inequality follows from Cauchy--Schwarz. Applying this to the complement handles the dense alternative of (3281:rodl).

Put $t=1/(a+1)$ and choose $\varepsilon=n^{-t}$ once this is below $1/2$. Then $m\geq n^t$, and the increasing function $m\mapsto m/(\varepsilon m+1)$ gives \[ \max(\alpha(G),\omega(G))\geq\tfrac12n^t. \] To meet the catalogue's coefficient-one normalization, choose a smaller positive exponent $c<t$, for instance initially $t/2$. For all large $n$, $n^c\leq n^t/2$. Decrease $c$ further if necessary to cover the finitely many remaining $n\geq2$, using $\max(\alpha,\omega)\geq2$ there; $n=0,1$ cause no difficulty. Thus (3281:rodl) implies exactly the supplied conclusion. The rate and normalization are both explicit; no generic asymptotic constant has been mistaken for coefficient one.

This calculation also tests slower sparsification. If the only available size guarantee were $|U|\geq n\exp(-C(\log(1/\varepsilon))^2)$, choosing $\log(1/\varepsilon)$ on the scale $\sqrt{\log n}$ would yield a homogeneous set of order $\exp(c\sqrt{\log n})$ by the same argument, not $n^c$. The gap is a polynomial-versus-superpolynomial loss in the accuracy parameter. Merely making a qualitative regularity statement effective would not close it.

Attempt II: falsify a strong recursive lemma.

A natural proposed induction asserts that every induced-$H$-free graph contains disjoint sets of size at least $\delta_H n$ with all or none of the edges between them. This is not a valid intermediate lemma for general $H$, already when $H=K_3$.

Fix $0<\delta<1/2$ and sample $G\sim G(n,p)$ with $p=n^{-3/4}$. The expected number of triangles is at most $n^{3/4}/6$, so by Markov's inequality it is at most $n^{7/8}$ with probability tending to one. There are at most $3^n$ ordered pairs of disjoint vertex sets. For any such pair with both sizes at least $\delta n$, the probability of having no crossing edge is at most \[ (1-p)^{\delta^2n^2}\leq\exp(-\delta^2n^{5/4}), \] and the probability of having all crossing edges is at most \[ p^{\delta^2n^2}=\exp(-\tfrac34\delta^2n^2\log n). \] A union bound shows that, with probability tending to one, neither type of pair exists anywhere in $G$.

Choose a graph with both properties and delete one vertex from each triangle, deleting at most $n^{7/8}$ vertices in total. The remaining graph $G'$ is triangle-free and has $n'=n-o(n)$ vertices. Any pure pair in $G'$ is also a pure pair in $G$. Given any proposed fixed linear fraction $\eta>0$, run the construction with $\delta=\eta/2$; then for large $n$, a pair of size $\eta n'$ would exceed $\delta n$ and is impossible. Hence there is no universal positive pure-pair fraction for triangle-free graphs.

This does not refute Erdős--Hajnal for $K_3$. Indeed, in a triangle-free graph every neighborhood is independent. If the maximum degree is at least $\sqrt n/2$, this gives a polynomial-size independent set; otherwise (3281:caro) gives one of order $\sqrt n$. The counterconstruction rules out the stronger induction step, not the much weaker homogeneous-set conclusion.

Attempt III: calibrate where recursive decomposition works.

For graphs built from one-vertex graphs by disjoint unions and complete joins, one can prove the useful invariant \begin{equation}\label{wsref-0-33-32-38-31-3a-70-72-6f-64-75-63-74} \alpha(G)\omega(G)\geq|V(G)|. \end{equation} For a disjoint union, $\alpha$ is the sum of the component independence numbers and $\omega$ their maximum, so the product is at least the sum of their products. For a complete join, interchange these roles. Induction proves (3281:product), hence a homogeneous set of size at least $\sqrt n$. This is a verified decomposition-based subcase. It does not assert that every $H$-free graph admits such a decomposition. The probabilistic example explains why trying to impose an equally strong recursive structure on all forbidden-induced-graph classes is not justified.

A more promising next step would be a density-reduction process whose logarithmic size loss is $O_H(\log(1/\varepsilon))$ in total, rather than a loss incurred anew at each accuracy scale. Such an amortized bound would imply (3281:rodl). No process with that bound for arbitrary $H$ is proved here; the known equivalence in [E1] warns that proving it is essentially the core problem, not a routine regularity estimate.

Stress test.

The random-graph alteration destroys every triangle while preserving the absence of large pure pairs, since deleting vertices cannot create one. The relevant probability estimates dominate the $3^n$ choices; no heuristic independence among different pairs is assumed. The sparsification calculation uses the complement only to extract a clique, not to change which graph $H$ is forbidden. Constants and small $n$ are handled explicitly.

The companion script checks (3281:caro) and (3281:product) on small exact graphs. A finite random sample is not used to certify the asymptotic counterexample: the union and Markov bounds above supply that proof. No stronger claim of a counterexample to Erdős--Hajnal follows from these method tests.

Outcome.

Outcome: Conditional reduction.

The argument quantifies the sparsification condition sufficient for the exact target and proves why a tempting linear-size pure-pair substitute fails. It also verifies a recursive class where the product invariant succeeds. Polynomial sparsification for every forbidden $H$ remains unproved here, so no extension of the known forbidden-graph range is claimed. These deductions are not presented as historically new results.

Sources

• S1 Lior Gishboliner and Ethan Honest, Disperse hypergraphs, Introduction $2025$. https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/disperse-hypergraphs/49C68DA657349D5D7BAB81EE3E971729. Catalogue formulation source.
• E1 Matija Bucić, Jacob Fox, and Huy Tuan Pham. Equivalence between Erdős--Hajnal and polynomial Rödl and Nikiforov conjectures, arXiv:2403.08303v2, 19 April 2024. Conjecture 2 and Theorem 7; the quantitative sparsification formulation and equivalence. https://arxiv.org/html/2403.08303v2. Consulted 27 September 2026 for the indicated result or scope.
• E2 Shenwei Huang, Yiao Ju, and Yidong Zhou. Erdős--Hajnal conjecture beyond five-vertex graphs, arXiv:2606.06258v3, 31 August 2026. Introduction and stated additional six-vertex cases. Recent preprint; not independently proof-audited here. https://arxiv.org/html/2606.06258v3. Consulted 27 September 2026 for the indicated result or scope.