Grassmann graph

From HandWiki
Short description: Class of simple graphs defined from vector spaces
Grassmann graph
Named afterHermann Grassmann
Vertices(nk)q
Edgesq[k]q[nk]q2(nk)q
Diametermin(k, nk)
PropertiesDistance-transitive
Connected
NotationJq(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, nk).
  • For all 0 ≤ d ≤ diam(Jq(n,k)), the intersection of any pair of vertices at distance d is (kd)-dimensional.
  • The clique number of Jq(n,k) is given by an expression in terms its least and greatest eigenvalues λ min and λ max:
ω(Jq(n,k))=1λmaxλmin

Automorphism group

There is a distance-transitive subgroup of Aut(Jq(n,k)) isomorphic to the projective linear group PΓL(n,q).

In fact, unless n=2k or k{1,n1}, Aut(Jq(n,k)) PΓL(n,q); otherwise Aut(Jq(n,k)) PΓL(n,q)×C2 or Aut(Jq(n,k)) Sym([n]q) respectively.[1]

Intersection array

As a consequence of being distance-transitive, Jq(n,k) is also distance-regular. Letting d denote its diameter, the intersection array of Jq(n,k) is given by {b0,,bd1;c1,cd} where:

  • bj:=q2j+1[kj]q[nkj]q for all 0j<d.
  • cj:=([j]q)2 for all 0<jd.

Spectrum

  • The characteristic polynomial of Jq(n,k) is given by
φ(x):=j=0diam(Jq(n,k))(x(qj+1[kj]q[nkj]q[j]q))((nj)q(nj1)q).[1]

See also

References

  1. 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.