The chromatic number of finite projective spaces

The chromatic number of the finite projective space $\mathrm{P}\mathrm{G}(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: $${\chi }_q(n)\le {\chi }_q(d)+{\chi }_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 $${\chi }_2(n)\le \lfloor 2n\mathrm{/}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 $${\chi }_2(n)\ge (1-o(1))\frac{n}{\log n}\mathrm{.}$$ We also consider ${\chi }_q(t;n)$, the minimum number of colors needed to color the points of $\mathrm{P}\mathrm{G}(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 ${\mathrm{\Omega }}_{q,t}(\log k)$ to $\mathrm{\Omega }(k)$.