Grassmann graph explained

Grassmann graph
Namesake:	Hermann Grassmann
Vertices:	\binom{n}{k} _{q}
Edges:	(q [k] _{q} [n - k] _{q})/(2) \binom{n}{k} _{q}
Properties:	Distance-transitive Connected

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

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

Graph-theoretic properties

• is isomorphic to .
• For all, the intersection of any pair of vertices at distance is -dimensional.
• The clique number of is given by an expression in terms its least and greatest eigenvalues and :

\omega \left( J _{q(n,k)} \right) = 1 - (λ _{max})/(λ _{min})

Automorphism 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 = 2 k 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) x C _{2} or \operatorname{Aut}(J _{q(n,k))} \cong \operatorname{Sym}([n] _{q)} respectively.^[1]

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 \left\{ b _{0,} \ldots, b _{d-1} ; c _{1,} \ldots c _{d} \right \} where:b _{j} : = q ^{2j} [k - j] _{q} [n - k - j] _{q} for all 0 \leq j < d .c _{j} : = ([j] ^{2} _{q)} for all 0 < j \leq d .

Spectrum

• The characteristic polynomial of

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

See also

• Grassmannian
• Johnson graph

References

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