Rainbow Triangles and the Erdős-Hajnal Problem in Projective Geometries
Abstract
We formulate a geometric version of the Erdős-Hajnal conjecture that applies to finite projective geometries rather than graphs, in both its usual 'induced' form and the multicoloured form. The multicoloured conjecture states, roughly, that a colouring c of the points of $PG(n-1,q)$ containing no copy of a fixed colouring c0 of $PG(k-1,q)$ for small k must contain a subspace of dimension polynomial in n that avoids some colour. If (k,q) = (2,2), then c0 is a colouring of a three-element 'triangle', and there are three essentially different cases, all of which we resolve. We derive both the cases where c0 assigns the same colour to two different elements from a recent breakthrough result in additive combinatorics due to Kelley and Meka. We handle the case that c0 is a 'rainbow' colouring by proving that rainbow-triangle-free colourings of projective geometries are exactly those that admit a certain decomposition into two-coloured pieces. This is closely analogous to a theorem of Gallai on rainbow-triangle-free coloured complete graphs. We also show that existing structure theorems resolve certain two-coloured cases where (k,q) = (2,3), and (k,q) = (3,2).
Related
- Vanishing theorems for L2 Dolbeault cohomology groups of projective Hartogs triangles
- On the solution to the Erdős-Hajnal problem on high-girth high-chromatic subgraphs
- The Erdős--Hajnal hypergraph Ramsey problem for r4(6,n)
- Absolutely universal projective embeddings of long-root geometries of orthogonal type
- Exact Area-Range Minima in the Quantitative Monsky Problem for Five and Seven Triangles
BibTeX
@article{chun2026rainbow,
title = {{Rainbow Triangles and the Erdős-Hajnal Problem in Projective Geometries}},
author = {Carolyn Chun and James Dylan Douthitt and Wayne Ge and Tony Huynh and Matthew E. Kroeker and Peter Nelson},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
month = oct,
doi = {10.37236/14754},
url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p5},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Rainbow Triangles and the Erdős-Hajnal Problem in Projective Geometries
AU - Carolyn Chun
AU - James Dylan Douthitt
AU - Wayne Ge
AU - Tony Huynh
AU - Matthew E. Kroeker
AU - Peter Nelson
PY - 2026
DA - 2026/10/09
JO - The Electronic Journal of Combinatorics
DO - 10.37236/14754
UR - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p5
AB - We formulate a geometric version of the Erdős-Hajnal conjecture that applies to finite projective geometries rather than graphs, in both its usual 'induced' form and the multicoloured form. The multicoloured conjecture states, roughly, that a colouring c of the points of $PG(n-1,q)$ containing no copy of a fixed colouring c_0 of $PG(k-1,q)$ for small k must contain a subspace of dimension polynomial in n that avoids some colour. If (k,q) = (2,2), then c_0 is a colouring of a three-element 'triangle', and there are three essentially different cases, all of which we resolve. We derive both the cases where c_0 assigns the same colour to two different elements from a recent breakthrough result in additive combinatorics due to Kelley and Meka. We handle the case that c_0 is a 'rainbow' colouring by proving that rainbow-triangle-free colourings of projective geometries are exactly those that admit a certain decomposition into two-coloured pieces. This is closely analogous to a theorem of Gallai on rainbow-triangle-free coloured complete graphs. We also show that existing structure theorems resolve certain two-coloured cases where (k,q) = (2,3), and (k,q) = (3,2).
SN - 1077-8926
ER -