|国家预印本平台
首页|Rainbow triangles and the Erd\H{o}s-Hajnal problem in projective geometries

Rainbow triangles and the Erd\H{o}s-Hajnal problem in projective geometries

Rainbow triangles and the Erd\H{o}s-Hajnal problem in projective geometries

来源:Arxiv_logoArxiv
英文摘要

We formulate a geometric version of the Erd\H{o}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 $\mathsf{PG}(n-1,q)$ containing no copy of a fixed colouring $c_0$ of $\mathsf{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)$.

Carolyn Chun、James Dylan Douthitt、Wayne Ge、Tony Huynh、Matthew E. Kroeker、Peter Nelson

数学

Carolyn Chun,James Dylan Douthitt,Wayne Ge,Tony Huynh,Matthew E. Kroeker,Peter Nelson.Rainbow triangles and the Erd\H{o}s-Hajnal problem in projective geometries[EB/OL].(2025-05-19)[2025-06-10].https://arxiv.org/abs/2505.13781.点此复制

评论