Grassmann graph

In graph theory, Grassmann graphs are a special class of simple graphs defined from systems of subspaces.

Uses your system voice; voice and rate in settings.

≈ 2 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

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 source

There 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 source

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,…,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 source

References

edit edit source
  1. ^ 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.

Words in each sectionAutomorphism groupAutomorphism groupAutomorphism group: 75 words75Graph-theoretic propert…Graph-theoretic propertiesGraph-theoretic properties: 73 words73Intersection arrayIntersection arrayIntersection array: 62 words62SpectrumSpectrumSpectrum: 40 words40See alsoSee alsoSee also: 6 words6
Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

Provenance

snapshot enwiki-001301284437 · captured 2025-07-18 · ledger · version history

Cite this page as: encyclopegia.org, “Grassmann graph”, snapshot enwiki-001301284437. https://encyclopegia.org/a/grassmann-graph