2025/12/01 by Anurag Bishnoi, Wouter Cames van Batenburg, Bishnoi, Anurag +3
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Topology and Set Theory #Computational Geometry and Mesh Generation
paper · pdf · doi:10.48550/arxiv.2512.01760
The chromatic number of the finite projective space PG(n-1,q), denoted χq(n), is the minimum number of colors needed to color its points so that no line is monochromatic. We prove subadditivity of χq(n) with respect to n, and then establish the following stronger recursive bound: χq(n)≤ χq(d)+χq(n+1-d)-1 for all 1 ≤ d < n. We use it to prove new upper bounds on χq(n). For q = 2, using this recursion we prove that χ2(n) ≤ \lfloor 2n/3 \rfloor + 1 for all n ≥ 2, and we show that this bound is tight for all n ≤ 7. In particular, our result recovers all previously known cases for n ≤ 6 and resolves the first open case n = 7. It also disproves a conjecture of Haddad that χ2(n) = n - 1 for all n ≥ 4, in a strong sense. On the lower-bound side, using a connection with multicolor Ramsey numbers for triangles, we note that χ2(n) ≥ (1 - o(1)) (n)/(log n). We also consider χq(t;n), the minimum number of colors needed to color the points of PG(n-1,q) with no monochromatic (t - 1)-dimensional subspace, and establish an equivalence between χq(t;n) and the multicolor vector-space Ramsey numbers Rq(t;k). Using this equivalence together with new upper bounds on χq(t;n), we improve, for every fixed t and q, the best known lower bounds on Rq(t;k) from Ωq,t(log k) to Ω(k).