Geometric Erdős–Hajnal conjecture for induced restrictions

Let PG(k1,q)\operatorname{PG}(k-1,q) and PG(n1,q)\operatorname{PG}(n-1,q) be projective geometries, identified with their point sets. For HPG(k1,q)H\subseteq\operatorname{PG}(k-1,q) and XPG(n1,q)X\subseteq\operatorname{PG}(n-1,q), say that XX contains HH as an induced restriction if there is an injective homomorphism ψ:PG(k1,q)PG(n1,q)\psi:\operatorname{PG}(k-1,q)\to\operatorname{PG}(n-1,q) such that, for every point xx, ψ(x)X\psi(x)\in X if and only if xHx\in H.

Geometric Erdős–Hajnal conjecture. For every prime power qq and all kNk\in\mathbb N and HPG(k1,q)H\subseteq\operatorname{PG}(k-1,q), there exist δ,C>0\delta,C>0 such that, for all nNn\in\mathbb N and XPG(n1,q)X\subseteq\operatorname{PG}(n-1,q) not containing HH as an induced restriction, there is a subspace WW of PG(n1,q)\operatorname{PG}(n-1,q) with dim(W)>Cnδ\dim(W)>Cn^\delta such that either WXW\subseteq X or WX=W\cap X=\varnothing.

This is the induced-restriction, two-colour specialization of the multicoloured geometric conjecture. Its general validity is open, and the source notes a stronger linear version as a further conjecture.

Sources & referencesView supporting material

Primary source

Carolyn Chun, James Dylan Douthitt, Wayne Ge, Tony Huynh, Matthew E. Kroeker and Peter Nelson, “Rainbow triangles and the Erdős-Hajnal problem in projective geometries”, arXiv:2505.13781 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.