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 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 - \frac$

Automorphism group

There is a distance-transitive subgroup of $\operatorname(J_q(n, k))$ isomorphic to the projective linear group $\operatorname(n, q)$.

In fact, unless $n = 2k$ or $k \in \$, $\operatorname(J_q(n,k)) \cong \operatorname(n, q)$; otherwise $\operatorname(J_q(n,k)) \cong \operatorname(n, q) \times C_2$ or \operatorname(J_q(n,k)) \cong \operatorname( 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 $\left\$ where:
* b_j := q^ - jq - k - jq for all $0 \leq j < d$.
* c_j := ( q)^2 for all $0 < j \leq d$.

Spectrum

*The characteristic polynomial of $J_q(n,k)$ is given by
:: \varphi(x) := \prod\limits_^ \left ( x - \left ( q^ - jq - k - jq - q \right ) \right )^{\left ( \binom{n}{j}_q - \binom{n}{j-1}_q \right )}.

See also

* Grassmannian
* Johnson graph

References

Parametric families of graphs
Regular graphs