Chromatic Number of Grassmann Graphs and MRD codes

Abstract

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 $\ddot{I}‡(J_q(n,m,t))\le (1+o(1))n^{m-t}{q}^{(n-m)(m-t)})$ when $n\ge 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 $\ddot{I}‡(J_q(n,m,t))=\hat{I}˜(q^{(m-t)\max (n-m,m)}).$