The chromatic number of finite projective spaces

Abstract

The chromatic number of the finite projective space $\mathrm{PG}(n-1,q)$, denoted ${\chi }_q(n)$, is the minimum number of colors needed to color its points so that no line is monochromatic. We prove subadditivity of ${\chi }_q(n)$ with respect to $n$, and then establish the following stronger recursive bound: \[ χ_q(n)\le χ_q(d)+χ_q(n+1-d)-1 \] for all $1\le d<n$. We use it to prove new upper bounds on ${\chi }_q(n)$. For $q=2$, using this recursion we prove that \[ χ_2(n) \le \lfloor 2n/3 \rfloor + 1 \] for all $n\ge 2$, and we show that this bound is tight for all $n\le 7$. In particular, our result recovers all previously known cases for $n\le 6$ and resolves the first open case $n=7$. It also disproves a conjecture of Haddad that ${\chi }_2(n)=n-1$ for all $n\ge 4$, in a strong sense. On the lower-bound side, using a connection with multicolor Ramsey numbers for triangles, we note that \[ χ_2(n) \ge (1 - o(1))\,\frac{n}{\log n}.\] We also consider ${\chi }_q(t;n)$, the minimum number of colors needed to color the points of $\mathrm{PG}(n-1,q)$ with no monochromatic $(t-1)$-dimensional subspace, and establish an equivalence between ${\chi }_q(t;n)$ and the multicolor vector-space Ramsey numbers $R_q(t;k)$. Using this equivalence together with new upper bounds on ${\chi }_q(t;n)$, we improve, for every fixed $t$ and $q$, the best known lower bounds on $R_q(t;k)$ from ${\Omega }_{q,t}(\log k)$ to $\Omega (k)$.

17 pages, 2 figures. New improved bounds for non-binary cases