Английская Википедия:Grassmann graph
Шаблон:Short description Шаблон:Infobox graph
In graph theory, Grassmann graphs are a special class of simple graphs defined from systems of subspaces. The vertices of the Grassmann graph Шаблон:Math are the Шаблон:Mvar-dimensional subspaces of an Шаблон:Mvar-dimensional vector space over a finite field of order Шаблон:Mvar; two vertices are adjacent when their intersection is Шаблон:Math-dimensional.
Many of the parameters of Grassmann graphs are [[Q-analog|Шаблон:Mvar-analogs]] of the parameters of Johnson graphs, and Grassmann graphs have several of the same graph properties as Johnson graphs.
Graph-theoretic properties
- Шаблон:Math is isomorphic to Шаблон:Math.
- For all Шаблон:Math, the intersection of any pair of vertices at distance Шаблон:Mvar is Шаблон:Math-dimensional.
- The clique number of Шаблон:Math is given by an expression in terms its least and greatest eigenvalues Шаблон:Math and Шаблон:Math:
- <math>\omega \left ( J_q(n,k) \right ) = 1 - \frac{\lambda_{\max}}{\lambda_{\min}}</math>
Automorphism group
There is a distance-transitive subgroup of <math>\operatorname{Aut}(J_q(n, k))</math> isomorphic to the projective linear group <math>\operatorname{P\Gamma L}(n, q)</math>.
In fact, unless <math>n = 2k</math> or <math>k \in \{ 1, n - 1 \}</math>, <math>\operatorname{Aut}(J_q(n,k))</math> Шаблон:Math <math>\operatorname{P\Gamma L}(n, q)</math>; otherwise <math>\operatorname{Aut}(J_q(n,k))</math> Шаблон:Math <math>\operatorname{P\Gamma L}(n, q) \times C_2</math> or <math>\operatorname{Aut}(J_q(n,k))</math> Шаблон:Math <math>\operatorname{Sym}([n]_q)</math> respectively.[1]
Intersection array
As a consequence of being distance-transitive, <math>J_q(n,k)</math> is also distance-regular. Letting <math>d </math> denote its diameter, the intersection array of <math>J_q(n,k)</math> is given by <math>\left\{ b_0, \ldots, b_{d-1}; c_1, \ldots c_d \right \} </math> where:
- <math>b_j := q^{2j + 1} [k - j]_q [n - k - j]_q </math> for all <math>0 \leq j < d </math>.
- <math>c_j := ([j]_q)^2 </math> for all <math>0 < j \leq d </math>.
Spectrum
- The characteristic polynomial of <math>J_q(n,k)</math> is given by
- <math>\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
