Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 4 / 4 / iv / Solution

The Grassmann graph is connected, and its distance can be determined directly. Put $C=A\cap B$, $r=\dim C$, and $s=k-r$. Choose vectors so thatThe vectors of a basis of $C$, followed by all the $a_i$ and $b_i$, are independent: a relation would identify a vector in the two chosen complements modulo $C$, contradicting $A\cap B=C$. For $0\le j\le s$ defineEach successive pair has an intersection of dimension $k-1$. Thus $A_0=A$ and $A_s=B$ are joined by a path of length $s$.

For the lower bound, if two vertices $U,V$ are adjacent, their common vector subspace $D$ has codimension one in each. Both $\dim (U\cap B)$ and $\dim (V\cap B)$ lie between $\dim (D\cap B)$ and $\dim (D\cap B)+1$. Thus one edge can change the dimension of the intersection with $B$ by at most one. It must change from $r$ to $k$ along a path from $A$ to $B$, requiring at least $k-r$ edges. Therefore

If two ordered pairs have equal distance, their intersections have equal dimension. Construct adapted bases for each pair as above and extend both to bases of the ambient vector space. The invertible linear map between them sends the first ordered pair to the second. It preserves intersection dimensions, so it is a graph automorphism. This proves that the Grassmann graph is distance-transitive, with the required simultaneous images. Its diameter is $k$, because $2k\le n$ permits two disjoint $k$-dimensional vector subspaces.