Grassmann graph
In graph theory, Grassmann graphs are a special class of simple graphs defined from systems of subspaces.
≈ 2 min read
Grassmann graph. encyclopegia.org, snapshot enwiki-001301284437. /a/grassmann-graph
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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
edit edit source- Jq(n, k) is isomorphic to Jq(n, n − k).
- For all 0 ≤ d ≤ diam(Jq(n,k)), the intersection of any pair of vertices at distance d is (k − d)-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[citation needed]
Automorphism group
edit edit sourceThere is a distance-transitive subgroup of Aut(Jq(n,k)) isomorphic to the projective linear group PΓL(n,q).[citation needed]
In fact, unless n=2k or k∈{1,n−1}, 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
edit edit sourceAs 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,…,bd−1;c1,…cd} where:
- bj:=q2j+1[k−j]q[n−k−j]q for all 0≤j<d.
- cj:=([j]q)2 for all 0<j≤d.
Spectrum
edit edit source- The characteristic polynomial of Jq(n,k) is given by
- φ(x):=∏j=0diam(Jq(n,k))(x−(qj+1[k−j]q[n−k−j]q−[j]q))((nj)q−(nj−1)q).[1]
See also
edit edit sourceReferences
edit edit source- ^ a b Brouwer, Andries E. (1989). Distance-Regular Graphs. Cohen, Arjeh M., Neumaier, Arnold. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 9783642743436. OCLC 851840609. Wikipedia revision 1301284437, retrieved 2026-11-18
Text derived from https://en.wikipedia.org/w/index.php?oldid=1301284437 under CC BY-SA 4.0; modifications have been made.