Grassmann graph

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.

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	min(k, n − k)
Properties	Distance-transitive Connected
Notation	Jq(n,k)
Table of graphs and parameters

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.

Graph-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:

${\displaystyle \omega \left(J_{q}(n,k)\right)=1-{\frac {\lambda _{\max }}{\lambda _{\min }}}}$ ^{[citation needed]}

Automorphism group

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

In fact, unless ${\displaystyle n=2k}$ or ${\displaystyle k\in \{1,n-1\}}$, ${\displaystyle \operatorname {Aut} (J_{q}(n,k))\cong \operatorname {P\Gamma L} (n,q)}$; otherwise ${\displaystyle \operatorname {Aut} (J_{q}(n,k))\cong \operatorname {P\Gamma L} (n,q)\times C_{2}}$ or ${\displaystyle \operatorname {Aut} (J_{q}(n,k))\cong \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]

See also

• Grassmannian
• Johnson graph