Grassmann graph

Grassmann graph
Grassmann graph
Named after	Hermann Grassmann
Vertices	(nk)q
Edges	q[k]q[n−k]q2(nk)q
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$ :

ω (J_{q} (n, k)) = 1 - \frac{λ_{\max}}{λ_{\min}}

^{[citation needed]}

Automorphism group

There is a distance-transitive subgroup of $Aut (J_{q} (n, k))$ isomorphic to the projective linear group $P Γ L (n, q)$ .^{[citation needed]}

In fact, unless $n = 2 k$ or $k \in {1, n - 1}$ , $Aut (J_{q} (n, k)) ≅ P Γ L (n, q)$ ; otherwise $Aut (J_{q} (n, k)) ≅ P Γ L (n, q) \times C_{2}$ or $Aut (J_{q} (n, k)) ≅ 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 ${b_{0}, \dots, b_{d - 1}; c_{1}, \dots c_{d}}$ where:

$b_{j} : = q^{2 j + 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

φ (x) : = \prod_{j = 0}^{diam (J_{q} (n, k))} {(x - (q^{j + 1} [k - j]_{q} [n - k - j]_{q} - [j]_{q}))}^{({(\binom{n}{j})}_{q} - {(\binom{n}{j - 1})}_{q})}

.^[1]

References

^ ^a ^b Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).

[:0-1] Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).

[1]

Grassmann graph

Contents

Graph-theoretic properties

Automorphism group

Intersection array

Spectrum

See also

References

Navigation menu

Grassmann graph

Graph-theoretic properties

Automorphism group

Intersection array

Spectrum

See also

References

Navigation menu

Search