Geometric Erdős–Hajnal conjecture for induced restrictions

About 1 year old · traced to

Let PG⁡(k−1,q)\operatorname{PG}(k-1,q) and PG⁡(n−1,q)\operatorname{PG}(n-1,q) be projective geometries, identified with their point sets. For H⊆PG⁡(k−1,q)H\subseteq\operatorname{PG}(k-1,q) and X⊆PG⁡(n−1,q)X\subseteq\operatorname{PG}(n-1,q), say that XX contains HH as an induced restriction if there is an injective homomorphism ψ:PG⁡(k−1,q)→PG⁡(n−1,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 x∈Hx\in H.

Geometric Erdős–Hajnal conjecture. For every prime power qq and all k∈Nk\in\mathbb N and H⊆PG⁡(k−1,q)H\subseteq\operatorname{PG}(k-1,q), there exist δ,C>0\delta,C>0 such that, for all n∈Nn\in\mathbb N and X⊆PG⁡(n−1,q)X\subseteq\operatorname{PG}(n-1,q) not containing HH as an induced restriction, there is a subspace WW of PG⁡(n−1,q)\operatorname{PG}(n-1,q) with dim⁡(W)>Cnδ\dim(W)>Cn^\delta such that either W⊆XW\subseteq X or W∩X=∅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.

References

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.