Erdős–Hajnal conjecture

Draw some dots and connect selected pairs with lines. A group can have every possible line within it, or no lines within it. Now forbid one particular small pattern, including its missing lines. Must every sufficiently large drawing then contain a large group of one of those two kinds? The conjecture predicts how that group's size grows as more dots are added.[1]

The question is whether excluding one fixed small graph forces a polynomial-sized clique or independent set in every larger graph. Both outcomes are uniform groups: every pair is adjacent in a clique, and every pair is nonadjacent in an independent set. Fix a finite graph $H$. A graph $G$ is $H$-free here when it has no induced copy of $H$, meaning that selecting vertices must reproduce both its edges and its absent edges. The conjecture asks for a constant $c(H)>0$ such that every such $n$-vertex graph has a clique or independent set with at least $n^{c(H)}$ vertices. The exponent depends on the fixed forbidden graph, rather than on the particular $G$ or its size.[1]

The predicted size grows as a positive power of the graph’s size. This is proved for selected forbidden patterns, but not every pattern.[1]

The June 2026 preprint, revised in August, extends selected cases without proving the universal assertion. The exponent may depend on H; it is not one constant for all forbidden graphs.[1]

A rule about a few dots could force order throughout a much larger network. Without such a rule, neither an all-connected group nor an all-disconnected group has to grow very quickly. The question is whether excluding any one fixed pattern always changes that limitation.[1]

For unrestricted graphs, some examples have neither type of group larger than a logarithmic scale. The conjecture predicts a polynomial guarantee after excluding any fixed induced pattern. A proof would identify a general source of this stronger order; results for particular forbidden graphs show that it can occur, but do not explain why it must occur for every pattern.[1]