Grassmann graph

Short description: Class of simple graphs defined from vector spaces

Grassmann graph
Named after	Hermann Grassmann
Vertices	${(\genfrac{}{}{0ex}{}{n}{k})}_q$
Edges	$\frac{q[k{]}_q[n-k{]}_q}{2}{(\genfrac{}{}{0ex}{}{n}{k})}_q$
Diameter	min(k, n – k)
Properties	Distance-transitive Connected
Notation	Jq(n,k)
Table of graphs and parameters

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.

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:

$\omega (J_q(n,k))=1-\frac{{\lambda }_{\max }}{{\lambda }_{\min }}$

Automorphism group

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

In fact, unless $n=2k$ or $k\in \{1,n-1\}$, $\mathrm{Aut}(J_q(n,k))$ ≅ $\mathrm{P}\mathrm{\Gamma }\mathrm{L}(n,q)$; otherwise $\mathrm{Aut}(J_q(n,k))$ ≅ $\mathrm{P}\mathrm{\Gamma }\mathrm{L}(n,q)\times C_2$ or $\mathrm{Aut}(J_q(n,k))$ ≅ $\mathrm{Sym}([n{]}_q)$ respectively.

Intersection 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 $\{b_0,\dots ,b_{d-1};c_1,\dots c_d\}$ where:

• $b_j:=q^{2j+1}[k-j{]}_q[n-k-j{]}_q$ for all $0\le j<d$.
• $c_j:=([j{]}_q{)}^2$ for all $0<j\le d$.

Spectrum

• The characteristic polynomial of $J_q(n,k)$ is given by

$\phi (x):=\prod _{j=0}^{\mathrm{diam}(J_q(n,k))}{(x-(q^{j+1}[k-j{]}_q[n-k-j{]}_q-[j{]}_q))}^{({(\genfrac{}{}{0ex}{}{n}{j})}_q-{(\genfrac{}{}{0ex}{}{n}{j-1})}_q)}$.

See also

• Grassmannian
• Johnson graph