Source-linked AI summary
The Erd\"os-Hajnal Conjecture---A Survey
Maria Chudnovsky
TL;DR
The conjecture asks whether every H-free graph has a clique or stable set of size at least |V(G)|^δ(H), while general graphs can lack such sets beyond O(log n). The paper surveys known results on the conjecture, including structural methods and weakenings for graphs and tournaments. Theorem 1.1 gives a c(H)-dependent lower bound for a clique or stable set in H-free graphs; Theorem 3.1 asserts disjoint subsets A, B, and Δ(T2, T2, T2) is a pseudo-celebrity but not a celebrity.
Problem
The conjecture asks whether every H-free graph has a clique or stable set of size at least |V(G)|^δ(H), while general graphs can lack such sets beyond O(log n).
Source: §1 · p. 1Method
Results
Theorem 1.1 gives a c(H)-dependent lower bound for a clique or stable set in H-free graphs; Theorem 3.1 asserts disjoint subsets A, B, and Δ(T2, T2, T2) is a pseudo-celebrity but not a celebrity.
Source: §1 · p. 1, §3 · p. 5, §6 · p. 11Takeaways & Limitations
The survey records progress on the conjecture without resolving its polynomial bound.
Source: §1 · p. 1
Abstract
from arXiv · showhide
The Erd\"os-Hajnal conjecture states that for every graph $H$, there exists a constant $\delta(H) > 0$ such that every graph $G$ with no induced subgraph isomorphic to $H$ has either a clique or a stable set of size at least $|V(G)|^{\delta(H)}$. This paper is a survey of some of the known results on this conjecture.
1 Introduction
The Erdős–Hajnal conjecture predicts polynomial-size cliques or stable sets in graphs excluding any fixed induced graph, despite general graphs allowing only logarithmic-size ones. This section states a partial result, notes that the conjecture remains open, and gives an equivalent formulation using large perfect induced subgraphs.
1 Introduction
- General graphs can have no clique or stable set larger than O(log n), motivating the conjecture that forbidding a fixed induced graph changes the bound.The cited theorem of Erdős establishes the general-graph example; Erdős and Hajnal proposed the conjecture.Source: §1 · p. 1
- For every fixed graph H, every H-free graph is conjectured to contain a clique or stable set of size at least |V(G)|^δ(H), for some δ(H) > 0.The paper calls this the Erdős–Hajnal conjecture.Source: §1 · p. 1
- A partial theorem gives every H-free graph a clique or stable-set bound parameterized by a positive constant c(H).The passage states the theorem but its displayed bound is incomplete.Source: §1 · p. 1
- The polynomial bound remains open, and the paper surveys recent results toward the conjecture.The authors describe the polynomial bound as harder to obtain.Source: §1 · p. 1
- An equivalent conjecture asks for a perfect induced subgraph of size at least |V(G)|^ψ(H), a single outcome that the authors say makes inductive proofs easier.The equivalence is stated to follow from Theorem 1.3.Source: §1 · p. 2
2 Graphs with the Erd¨os-Hajnal property
This section surveys established Erdős–Hajnal cases and structural approaches, including closure under substitution and a narrowness framework. It also records unresolved graphs and a conjectured strengthening for graphs excluding both H and its complement.
Graphs with the Erdős–Hajnal property
- Substitution preserves the Erdős–Hajnal property, and the paper describes it as the only known operation for building larger graphs with the property from smaller ones.The proof uses induced copies of the component graphs and a counting argument to force a forbidden substituted copy.Source: §2 · p. 3
- All graphs on at most four vertices, and all five-vertex graphs other than the five-cycle and complement of the four-edge path, have the property.The bull is the remaining listed prime five-vertex case, established separately in Theorem 2.3.Source: §2 · pp. 3–4
- The paper introduces α-narrowness as a route to proving the Erdős–Hajnal property: showing all H-free graphs are α-narrow is sufficient, and the corresponding conjecture is equivalent to the original one.The equivalence is attributed to Fox (see); the paper says narrowness is more convenient for structural proofs.Source: §2 · p. 4
- Every bull-free graph has the Erdős–Hajnal property, equivalently expressed here as every bull-free graph being 2-narrow.The bull result is proved structurally for prime graphs and by induction otherwise.Source: §2 · p. 4
- For bull-free graphs, α-narrowness is preserved under substitution, supplying the inductive step for the non-prime case.Source: §2 · p. 4
- The conjecture remains open for the four-edge path, its complement, and the five-cycle, and no prime graph on at least six vertices is known to have the property.Source: §2 · p. 5
- Every graph with no induced four-edge path or its complement is 2-narrow; every prime graph in this class is either perfect or isomorphic to the five-cycle.Source: §2 · p. 5
- The section proposes that excluding both H and its complement may suffice for the Erdős–Hajnal bound; this is proved for the five-edge path.The five-edge-path case strengthens a result of, as reported in.Source: §2 · p. 5
3 Approximate results
This section presents weakenings of the Erdős–Hajnal conjecture that hold for all graphs. They provide homogeneous pairs or an asymptotic typicality result rather than the conjectured guarantee for every graph.
Approximate results
- Every H-free graph contains disjoint sets A and B that are either complete or anticomplete to one another.The proof partitions the vertices into candidate sets and builds a possible induced H one vertex at a time; H-freeness eventually yields the pair.Source: §3 · p. 5
- For H-free graphs with ω(G) < |V(G)|^δ(H), the strengthened result guarantees disjoint sets A and B that are anticomplete.The theorem’s displayed text does not include the other stated properties of the sets.Source: §3 · p. 6
- For each H, the proportion of H-free graphs with a clique or stable set of size at least n^ε(H) tends to 1 as n tends to infinity.The proof uses Szemerédi’s Regularity Lemma and Theorem 2.3.Source: §3 · p. 6
4 Tournaments
The section develops the Erdős–Hajnal property for tournaments, where large transitive subtournaments play a role analogous to cliques and stable sets. It gives several classes with the property, including all tournaments on at most five vertices.
Tournament analogue
- The conjectured tournament analogue asks whether every S-free tournament contains a transitive subtournament of size at least |V(T)|^δ(S).The section motivates transitive subtournaments as an analogue of both cliques and stable sets.Source: §4 · p. 6
Substitution
- Substitution preserves the Erdős–Hajnal property for tournaments whose two input tournaments have the property.Source: §4 · pp. 6–7
Galaxies
- Every galaxy has the Erdős–Hajnal property, and the proof constructs a forbidden copy using regular partitions and backward edges.The proof starts from a regular partition and uses dense pairs of parts; if substantial subsets are complete to one another, induction gives a large transitive subtournament.Source: §4 · pp. 7–8
Proof tools
- A directed regularity theorem provides bounded-size ε-regular partitions, and a separate embedding lemma guarantees a copy of H when every pair of parts is regular and has both directed densities at least λ.The partition has m ≤ k ≤ DM parts; the embedding lemma applies when η is sufficiently small relative to k and λ.Source: §4 · p. 8
Small tournaments
- Every tournament on at most five vertices has the Erdős–Hajnal property, including the unique five-vertex tournament S5 that is not a galaxy.Theorem 4.5 establishes the property for S5; together with the galaxy result, this yields the five-vertex conclusion.Source: §4 · p. 8
Further examples
- For every k, the tournament Pk has the Erdős–Hajnal property because it has a galaxy ordering..Source: §4 · p. 8
5 Linear-size cliques, stable sets and transitive subtournaments
The section characterizes when excluding tournaments ensures linear-size transitive subtournaments and proposes a criterion for finite graph families to force linear-size cliques or stable sets. It also relates these properties to bounded covering numbers and states an open conjecture for infinite families.
Linear-size transitive subtournaments
- For tournaments, a celebrity is one whose exclusion guarantees a transitive subtournament of linear size; the section contrasts this classification problem with the graph case.The text says the corresponding graph question is uninteresting because such a graph must have at most two vertices.Source: §5 · p. 9
Tournament celebrities
- A tournament is a celebrity exactly when its strongly connected components are celebrities and, if strongly connected with more than one vertex, it has form Δ(S, Tk, T1) or Δ(S, T1, Tk).The section also states that a tournament is a hero exactly when it is a celebrity.Source: §5 · p. 9
Graph-family properties
- For finite graph families, being heroic means bounded cochromatic number on every family-free graph, while being celebrated means a linear-size clique or stable set.Every heroic family is celebrated.Source: §5 · p. 9
Necessary conditions
- Every celebrated graph family must contain a complete multipartite graph, its complement, a forest, and a forest complement; thus a single graph can force linear size only when it has at most two vertices.The stated necessity uses multipartite examples and graphs of arbitrarily large girth with no linear-size stable set.Source: §5 · pp. 9–10
Finite heroic families
- A finite graph family is conjectured heroic if and only if it contains a complete multipartite graph, its complement, a forest, and a forest complement.The conjecture extends the complete-graph/tree formulation, and the paper states the two conjectures are equivalent.Source: §5 · p. 10
Infinite families
- For every complete graph K and integer t > 0, the family containing K and all cycles of length at least t is conjectured heroic.If true, this would be a heroic family without a minimal heroic set.Source: §5 · p. 10
6 Near-linear transitive subtournaments
This section studies EH-coefficients and their suprema, including the distinction between a supremum and an attainable coefficient. It reports structural characterizations and a threshold result for tournaments with EH-supremum near 1.
6 Near-linear transitive subtournaments
- Conjecture 6.1 asks whether every tournament has a positive EH-coefficient; ξ(S) is the supremum of S’s EH-coefficients and need not itself be one.An exponent ε is an EH-coefficient when every S-free tournament T satisfies α(T) ≥ c|V(T)|^ε for some c > 0.Source: §6 · pp. 10–11
- Pseudo-heroes and pseudo-celebrities coincide, and a tournament is a pseudo-hero exactly when all its strongly connected components are pseudo-heroes.Prior work describes all pseudo-heroes and pseudo-celebrities explicitly.Source: §6 · p. 11
- For strongly connected tournaments with more than one vertex, the theorem lists ∆(S,T1,Tk) and ∆(S,Tk,T1) forms with pseudo-hero S and k > 0.Source: §6 · p. 11
- ∆(T2,T2,T2) is a pseudo-celebrity but not a celebrity, so its EH-supremum is not attained as an EH-coefficient.Source: §6 · p. 11
- Every tournament S with ξ(S) > 5/6 is a pseudo-hero and therefore has ξ(S) = 1; the section also reports a gap after 1 among EH-suprema.The cited characterization identifies pseudo-heroes as tournaments that are S-free for a particular six-tournament family, including S5.Source: §6 · pp. 11–12