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 $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)$.