Grassmann graph
| Grassmann graph | |
|---|---|
| Named after | Hermann Grassmann |
| Vertices | [math]\displaystyle{ \binom{n}{k}_q }[/math] |
| Edges | [math]\displaystyle{ \frac{q [k]_q [n - k]_q}{2} \binom{n}{k}_q }[/math] |
| 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 Jq(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
- Jq(n, k) is isomorphic to Jq(n, n – k).
- For all 0 ≤ d ≤ diam(Jq(n,k)), the intersection of any pair of vertices at distance d is (k – d)-dimensional.
- The clique number of Jq(n,k) is given by an expression in terms its least and greatest eigenvalues λ min and λ max:
- [math]\displaystyle{ \omega \left ( J_q(n,k) \right ) = 1 - \frac{\lambda_{\max}}{\lambda_{\min}} }[/math]
Automorphism group
There is a distance-transitive subgroup of [math]\displaystyle{ \operatorname{Aut}(J_q(n, k)) }[/math] isomorphic to the projective linear group [math]\displaystyle{ \operatorname{P\Gamma L}(n, q) }[/math].
In fact, unless [math]\displaystyle{ n = 2k }[/math] or [math]\displaystyle{ k \in \{ 1, n - 1 \} }[/math], [math]\displaystyle{ \operatorname{Aut}(J_q(n,k)) }[/math] ≅ [math]\displaystyle{ \operatorname{P\Gamma L}(n, q) }[/math]; otherwise [math]\displaystyle{ \operatorname{Aut}(J_q(n,k)) }[/math] ≅ [math]\displaystyle{ \operatorname{P\Gamma L}(n, q) \times C_2 }[/math] or [math]\displaystyle{ \operatorname{Aut}(J_q(n,k)) }[/math] ≅ [math]\displaystyle{ \operatorname{Sym}([n]_q) }[/math] respectively.[1]
Intersection array
As a consequence of being distance-transitive, [math]\displaystyle{ J_q(n,k) }[/math] is also distance-regular. Letting [math]\displaystyle{ d }[/math] denote its diameter, the intersection array of [math]\displaystyle{ J_q(n,k) }[/math] is given by [math]\displaystyle{ \left\{ b_0, \ldots, b_{d-1}; c_1, \ldots c_d \right \} }[/math] where:
- [math]\displaystyle{ b_j := q^{2j + 1} [k - j]_q [n - k - j]_q }[/math] for all [math]\displaystyle{ 0 \leq j \lt d }[/math].
- [math]\displaystyle{ c_j := ([j]_q)^2 }[/math] for all [math]\displaystyle{ 0 \lt j \leq d }[/math].
Spectrum
- The characteristic polynomial of [math]\displaystyle{ J_q(n,k) }[/math] is given by
- [math]\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 )} }[/math].[1]
See also
References
- ↑ 1.0 1.1 Brouwer, Andries E. (1989). Distance-Regular Graphs. Cohen, Arjeh M., Neumaier, Arnold.. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783642743436. OCLC 851840609. https://www.worldcat.org/oclc/851840609.
 |  |
