Grassmann graph

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

Grassmann Graph
Named after	Hermann Grassmann
Vertices	${\displaystyle {\binom {n}{k}}_{q}}$
Edges	${\displaystyle {\frac {q[k]_{q}[n-k]_{q}}{2}}{\binom {n}{k}}_{q}}$
Diameter	${\displaystyle \min(k,n-k)}$
Properties	Distance-transitive Connected
Notation	${\displaystyle J_{q}(n,k)}$
Table of graphs and parameters

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

Graph-theoretic properties

• ${\displaystyle J_{q}(n,k)}$ is isomorphic to ${\displaystyle J_{q}(n,n-k)}$.
• For all ${\displaystyle 0\leq d\leq \operatorname {diam} (J_{q}(n,k))}$, the intersection of any pair of vertices at distance ${\displaystyle d}$ is ${\displaystyle (k-d)}$-dimensional.
• ${\displaystyle \omega \left(J_{q}(n,k)\right)=1-{\frac {\lambda _{\max }}{\lambda _{\min }}},}$ which is to say that the clique number of ${\displaystyle J_{q}(n,k)}$ is given by an expression in terms its least and greatest eigenvalues ${\displaystyle \lambda _{\min }}$and ${\displaystyle \lambda _{\max }}$.

Automorphism group

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

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

Intersection array

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

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

Spectrum

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

${\displaystyle \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)}}$.[1]

References

1. Brouwer, Andries E. (1989). Distance-Regular Graphs. Cohen, Arjeh M., Neumaier, Arnold. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783642743436. OCLC 851840609.