Encyclopedia

Grassmann graph

Class of simple graphs defined from vector spaces

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated July 19, 2025

In graph theory, Grassmann graphs are a special class of simple graphs defined from systems of subspaces. The vertices of the Grassmann graph J_q(n, k) are the k-dimensional subspaces of an n-dimensional vector space over a finite field of order q; two vertices are adjacent when their intersection is (k − 1)-dimensional.

Many of the parameters of Grassmann graphs are q-analogs of the parameters of Johnson graphs, and Grassmann graphs have several of the same graph properties as Johnson graphs.

01Graph-theoretic properties

J_q(n, k) is isomorphic to J_q(n, n − k).
For all 0 ≤ d ≤ diam(J_q(n,k)), the intersection of any pair of vertices at distance d is (k − d)-dimensional.
The clique number of J_q(n,k) is given by an expression in terms its least and greatest eigenvalues λ_min and λ_max:

$\omega \left(J_{q}(n,k)\right)=1-{\frac {\lambda _{\max }}{\lambda _{\min }}}$

02Automorphism group

There is a distance-transitive subgroup of $\operatorname {Aut} (J_{q}(n,k))$ isomorphic to the projective linear group $\operatorname {P\Gamma L} (n,q)$ .

In fact, unless $n=2k$ or $k\in \{1,n-1\}$ , $\operatorname {Aut} (J_{q}(n,k))\cong \operatorname {P\Gamma L} (n,q)$ ; otherwise $\operatorname {Aut} (J_{q}(n,k))\cong \operatorname {P\Gamma L} (n,q)\times C_{2}$ or $\operatorname {Aut} (J_{q}(n,k))\cong \operatorname {Sym} ([n]_{q})$ respectively.

03Intersection array

As a consequence of being distance-transitive, $J_{q}(n,k)$ is also distance-regular. Letting $d$ denote its diameter, the intersection array of $J_{q}(n,k)$ is given by $\left\{b_{0},\ldots ,b_{d-1};c_{1},\ldots c_{d}\right\}$ where:

$b_{j}:=q^{2j+1}[k-j]_{q}[n-k-j]_{q}$ for all $0\leq j<d$ .
$c_{j}:=([j]_{q})^{2}$ for all $0<j\leq d$ .

04Spectrum

The characteristic polynomial of $J_{q}(n,k)$ is given by

$\varphi (x):=\prod \limits _{j=0}^{\operatorname {diam} (J_{q}(n,k))}\left(x-\left(q^{j+1}[k-j]_{q}[n-k-j]_{q}-[j]_{q}\right)\right)^{\left({\binom {n}{j}}_{q}-{\binom {n}{j-1}}_{q}\right)}$ .

Watch videos about Grassmann graphExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Grassmann graph”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.