Grassmann graph

{{Short description|Class of simple graphs defined from vector spaces}}

{{Infobox graph

|name=Grassmann graph

|namesake=Hermann Grassmann

|notation={{math|J{{sub|q}}(n,k)}}

|vertices= $\binom{n}{k}_q$

|edges= $\frac{q [k]_q [n - k]_q}{2} \binom{n}{k}_q$

|properties=Distance-transitive
Connected

|diameter={{math|min(k, n − k)}}

}}

In graph theory, Grassmann graphs are a special class of simple graphs defined from systems of subspaces. The vertices of the Grassmann graph {{math|J{{sub|q}}(n, k)}} are the {{mvar|k}}-dimensional subspaces of an {{mvar|n}}-dimensional vector space over a finite field of order {{mvar|q}}; two vertices are adjacent when their intersection is {{math|(k − 1)}}-dimensional.

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

Graph-theoretic properties

{{math|J{{sub|q}}(n, k)}} is isomorphic to {{math|J{{sub|q}}(n, n − k)}}.
For all {{math|0 ≤ d ≤ diam(J{{sub|q}}(n,k))}}, the intersection of any pair of vertices at distance {{mvar|d}} is {{math|(k − d)}}-dimensional.
The clique number of {{math|J{{sub|q}}(n,k)}} is given by an expression in terms its least and greatest eigenvalues {{math|λ{{sub| min}}}} and {{math|λ{{sub| max}}}}:

:: $\omega \left( J_q(n,k) \right) = 1 - \frac{\lambda_{\max}}{\lambda_{\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)$ .{{Citation needed|date=August 2024}}

In fact, unless $n = 2k$ 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) \times C_2$ or $\operatorname{Aut}(J_q(n,k)) \cong \operatorname{Sym}([n]_q)$ respectively.{{Cite book|url=https://www.worldcat.org/oclc/851840609|title=Distance-Regular Graphs|last=Brouwer|first=Andries E.|date=1989|publisher=Springer Berlin Heidelberg|others=Cohen, Arjeh M., Neumaier, Arnold.|isbn=9783642743436|location=Berlin, Heidelberg|oclc=851840609}}

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 + 1} [k - j]_q [n - k - j]_q$ for all $0 \leq j < d$ .
$c_j := ([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_{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 )}$ .

References

Category:Parametric families of graphs

Category:Regular graphs