The chromatic number of finite projective spaces
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917529542197248 |
|---|---|
| author | Bishnoi, Anurag van Batenburg, Wouter Cames Ravi, Ananthakrishnan |
| author_facet | Bishnoi, Anurag van Batenburg, Wouter Cames Ravi, Ananthakrishnan |
| contents | The chromatic number of the finite projective space $\mathrm{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)\le χ_q(d)+χ_q(n+1-d)-1 \] for all $1 \leq d < n$. We use it to prove new upper bounds on $χ_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 $χ_2(n) = n - 1$ for all $n \geq 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 $χ_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 $χ_q(t;n)$ and the multicolor vector-space Ramsey numbers $R_q(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 $R_q(t;k)$ from $Ω_{q,t}(\log k)$ to $Ω(k)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_01760 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The chromatic number of finite projective spaces Bishnoi, Anurag van Batenburg, Wouter Cames Ravi, Ananthakrishnan Combinatorics 51E10, 51E20, 05D10 The chromatic number of the finite projective space $\mathrm{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)\le χ_q(d)+χ_q(n+1-d)-1 \] for all $1 \leq d < n$. We use it to prove new upper bounds on $χ_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 $χ_2(n) = n - 1$ for all $n \geq 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 $χ_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 $χ_q(t;n)$ and the multicolor vector-space Ramsey numbers $R_q(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 $R_q(t;k)$ from $Ω_{q,t}(\log k)$ to $Ω(k)$. |
| title | The chromatic number of finite projective spaces |
| topic | Combinatorics 51E10, 51E20, 05D10 |
| url | https://arxiv.org/abs/2512.01760 |