Grassmann graph

Grassmann graph
Grassmann graph
Named after	Hermann Grassmann
Vertices
Edges
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 $J q (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

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

\omega \left(J_{q}(n,k)\right)=1-{\frac {\lambda _{\max }}{\lambda _{\min }}}

^{[citation needed]}

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]}

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.^[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+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)}

.^[1]

References

^ ^a ^b Brouwer, Andries E. (1989). Distance-Regular Graphs. Cohen, Arjeh M., Neumaier, Arnold. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783642743436. OCLC 851840609.

[:0-1] Brouwer, Andries E. (1989). Distance-Regular Graphs. Cohen, Arjeh M., Neumaier, Arnold. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783642743436. OCLC 851840609.

[1]