The Erdős-Hajnal conjecture asserts that, for every fixed graph 
, there exists 
such that every graph 
on 
vertices with no induced
subgraph isomorphic to 
has either a clique or an independent
vertex set of size at least 
.
The exponent may depend on 
but not on 
(Chun et al. 2026). The conjecture is problem
61 in the Erdős problems collection (Bloom
2026).
A geometric analog concerns colorings of the points of finite projective spaces 
. For a fixed forbidden coloring of 
, it asks for a projective
subspace whose underlying vector space has dimension at least 
and on which some color is absent, where 
depend on the forbidden coloring, the field,
and the number of colors. For the three-point line 
, Chun et al. (2026, Theorem 5) resolve
the monochromatic and two-color forbidden patterns for any fixed number of colors,
with 
. For the rainbow pattern, they resolve the
case of three-colorings with 
and 
(Chun et al. 2026, Theorem 6). These are
cases of the geometric analog; the general graph conjecture remains open.
More generally, if every line of 
receives at most two colors, there is a chain of subspaces
from the empty set to the entire geometry such that each successive difference receives
at most two colors (Chun et al. 2026, Theorem 7). If exactly 
colors are used, there is a maximal chain whose successive
differences are monochromatic in distinct colors (Chun et al. 2026, Theorem 8).
Huang et al. (2026, Theorem 1.1) proved the graph conjecture when the forbidden graph is any fixed path
graph 
. For every positive
integer 
, there is 
such that every finite simple graph on 
vertices with no induced subgraph isomorphic
to 
has a clique or an independent
vertex set of size at least 
.
This settles the path case, while the conjecture for arbitrary forbidden graphs
remains open. Huang et al. (2026) report developing the proof
through dialogue with Claude Opus 5.5 and ChatGPT-6, then checking each step. A Lean
formalization is supplied.
