Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.10777 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911440167763968 |
|---|---|
| author | D'haeseleer, Jozefien Pavese, Francesco Santonastaso, Paolo Taranchuk, Vladislav |
| author_facet | D'haeseleer, Jozefien Pavese, Francesco Santonastaso, Paolo Taranchuk, Vladislav |
| contents | In this paper we investigate the chromatic number of the Grassmann graphs and of their powers, denoted $J_q(n,m,t)$. In this graph, the vertices correspond to the $m$-dimensional subspaces in $\mathbb{F}_q^n$ and two vertices are adjacent if the corresponding subspaces intersect in a subspace of dimension at least $t$.
By generalizing the lifting technique of Silva, Kötter and Kschischang, we use \emph{maximum rank distance (MRD)} codes to establish that $χ(J_q(n, m, t)) \leq (1 +o(1))n^{m-t}q^{(n-m)(m-t)})$ when $n \geq 2m$. Given that $J_q(n, m, t)$ is isomorphic to $J_q(n,n-m,n-2m+t)$, this establishes a new upper bound on $J_q(n, m, t)$ for any valid choice of parameters. Furthermore, we observe that in the regime that $n, m $, and $t$ are fixed, our bound is asymptotically tight, implying that $
χ(J_q(n, m, t)) = Θ(q^{(m-t)\max(n-m, m)}). $ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_10777 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Chromatic Number of Grassmann Graphs and MRD codes D'haeseleer, Jozefien Pavese, Francesco Santonastaso, Paolo Taranchuk, Vladislav Combinatorics 05C15 In this paper we investigate the chromatic number of the Grassmann graphs and of their powers, denoted $J_q(n,m,t)$. In this graph, the vertices correspond to the $m$-dimensional subspaces in $\mathbb{F}_q^n$ and two vertices are adjacent if the corresponding subspaces intersect in a subspace of dimension at least $t$. By generalizing the lifting technique of Silva, Kötter and Kschischang, we use \emph{maximum rank distance (MRD)} codes to establish that $χ(J_q(n, m, t)) \leq (1 +o(1))n^{m-t}q^{(n-m)(m-t)})$ when $n \geq 2m$. Given that $J_q(n, m, t)$ is isomorphic to $J_q(n,n-m,n-2m+t)$, this establishes a new upper bound on $J_q(n, m, t)$ for any valid choice of parameters. Furthermore, we observe that in the regime that $n, m $, and $t$ are fixed, our bound is asymptotically tight, implying that $ χ(J_q(n, m, t)) = Θ(q^{(m-t)\max(n-m, m)}). $ |
| title | Chromatic Number of Grassmann Graphs and MRD codes |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2602.10777 |