Grassmann graph

• ${\displaystyle J_{q}(n,k)}$ is isomorphic to ${\displaystyle J_{q}(n,n-k)}$.
• For all ${\displaystyle 0\leq d\leq \operatorname {diam} (J_{q}(n,k))}$, the intersection of any pair of vertices at distance ${\displaystyle d}$ is ${\displaystyle (k-d)}$-dimensional.
• ${\displaystyle \omega \left(J_{q}(n,k)\right)=1-{\frac {\lambda _{\max }}{\lambda _{\min }}},}$ which is to say that the clique number of ${\displaystyle J_{q}(n,k)}$ is given by an expression in terms its least and greatest eigenvalues ${\displaystyle \lambda _{\min }}$and ${\displaystyle \lambda _{\max }}$.

There is a distance-transitive subgroup of ${\displaystyle \operatorname {Aut} (J_{q}(n,k))}$ isomorphic to the projective linear group ${\displaystyle \operatorname {PGL} (n,q)}$.

In fact, unless ${\displaystyle n=2k}$ or ${\displaystyle k\in \{1,n-1\}}$, ${\displaystyle \operatorname {Aut} (J_{q}(n,k))}$ ≅ ${\displaystyle \operatorname {PGL} (n,q)}$; otherwise ${\displaystyle \operatorname {Aut} (J_{q}(n,k))}$ ≅ ${\displaystyle \operatorname {PGL} (n,q)\times C_{2}}$or ${\displaystyle \operatorname {Aut} (J_{q}(n,k))}$ ≅ ${\displaystyle \operatorname {Sym} ([n]_{q})}$ respectively.[1]

As a consequence of being distance-transitive, ${\displaystyle J_{q}(n,k)}$ is also distance-regular. Letting ${\displaystyle d}$ denote its diameter, the intersection array of ${\displaystyle J_{q}(n,k)}$ is given by ${\displaystyle \left\{b_{0},\ldots ,b_{d-1};c_{1},\ldots c_{d}\right\}}$ where:

• ${\displaystyle b_{j}:=q^{2j+1}[k-j]_{q}[n-k-j]_{q}}$ for all ${\displaystyle 0\leq j<d}$.
• ${\displaystyle c_{j}:=([j]_{q})^{2}}$ for all ${\displaystyle 0<j\leq d}$.

• The characteristic polynomial of ${\displaystyle J_{q}(n,k)}$ is given by

${\displaystyle \varphi (x):=\prod \limits _{j=0}^{\operatorname {diam} (J_{q}(n,k))}\left(x-\left(q^{j+1}[k-j]_{q}[n-k-j]_{q}-[j]_{q}\right)\right)^{\left({\binom {n}{j}}_{q}-{\binom {n}{j-1}}_{q}\right)}}$.[1]

• Grassmannian
• Johnson graph