Up

Grassmann graphs

Hermann Grassmann (1809-1877) started out as a banker, then became mathematician and introduced the manifold of subspaces of a vector space, and invented exterior algebra. At the age of 53 he turned from mathematics to Indoeuropean, especially Sanskrit, studies, where Grassmann's law is still well-known:

(1) Given a root with final aspirate and an initial consonant capable of aspiration, and given also that the final element loses aspiration (by some separate sound law), then that feature is retracted to the initial element.
(E.g., in Greek: θριξ, gen. τριχος.)
(2) Given two consonant groups in a word, separated by a vowel and themselves aspirated, and provided that they are within the same root, then one (and normally the first) is deprived of its breath feature.
(E.g., in Greek: θιθημι becomes τιθημι.)

Consider a vector space V of dimension d over the finite field with q elements. Make a graph with as vertices the subspaces of dimension e of V, where two subspaces are adjacent when they meet in a hyperplane of each. The resulting graph is called the Grassmann graph Grassmann(d,e)q.

This graph is distance-regular, with diameter min(e,de). For the parameters, see [BCN], 9.3.3.

In particular, for e = 2, we find a strongly regular graph (of the lines in a projective space, adjacent when they meet). This graph is strongly regular, with parameters
v = (qd − 1)(qd−1 − 1) / (q2 − 1)(q − 1),
k = q(q+1)(qd−2 − 1)/(q − 1),
λ = (qd−1 − 1)/(q − 1) + q2 − 2,
μ = (q+1)2.

The eigenvalues are
r = q2(qd−3 − 1)/(q − 1) − 1
s = −q−1,
with multiplicities
f = (qd − 1)/(q − 1) − 1,
g = (qd − 1)(qd−1 − 1) / (q2 − 1)(q − 1) − (qd − 1)/(q − 1).