Grassmann Graph

The Grassmann graph J_q(n,k) is defined such that the vertices are the k-dimensional subspaces of an n-dimensional finite field of order q and edges correspond to pairs of vertices whose intersection is (k-1)-dimensional.

J_q(n,k) has vertex count (n; k)_q, where (n; k)_q is a q-binomial, and edge count

 m(J_q(n,k))=1/2q[k]_q[n-k]_q(n; k)_q.

J_q(n,k) is isomorphic to J_q(n,n-k).

The graph J_2(4,2) is related to Kirkman's schoolgirl problem.

Grassmann graphs are distance-transitive and therefore also distance-regular.

Many parameters of J_q(n,k) are q-analogs of the corresponding parameters of the Johnson graph J(n,k).

See also

Distance-Regular Graph, Distance-Transitive Graph, Johnson Graph, Kirkman's Schoolgirl Problem

Explore with Wolfram|Alpha


Brouwer, A. "Grassmann Graphs.", A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, 1989.

Cite this as:

Weisstein, Eric W. "Grassmann Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications