= Solution
For the <Johnson graph>, an <edge> exchanges one member of a $k$-set. Along one <edge>, intersection size with a fixed target can increase by at most one, so any <path in a graph> from $A$ to $B$ has length at least $k-|A\cap B|$. Replacing the elements of $A\setminus B$ successively by elements of $B\setminus A$ gives a <path in a graph> attaining that bound. Hence the <distance in a Johnson graph> is
$$
\boxed{d(A,B)=k-|A\cap B|.}
$$
If two ordered pairs have the same distance $r$, their four regions (intersection, first-only, second-only and outside the union) have sizes $k-r,r,r,n-k-r$. Choose bijections between corresponding regions. Their union is a ground-set <permutation> sending the ordered pair to the other pair and preserving <graph adjacency>. \b[The <symmetric group> is <distance-transitive>.] For $n\ge2k$ the <graph diameter> is $k$.
For the <Grassmann graph>, a codimension-one exchange changes intersection <dimension> with a fixed target by at most one. More explicitly, if $A,A'$ are adjacent, their common $(k-1)$-space shows $\dim(A'\cap B)\ge\dim(A\cap B)-1$, and exchanging the two gives the reverse bound. Thus distance is at least $r=k-\dim(A\cap B)$.
Choose a <basis> $c_1,\ldots,c_{k-r}$ of $I=A\cap B$, complement it in $A$ by $a_1,\ldots,a_r$, and in $B$ by $b_1,\ldots,b_r$. These combined vectors are independent because $A\cap B=I$. The spaces
$$
A_j=I+\langle b_1,\ldots,b_j,a_{j+1},\ldots,a_r\rangle,\qquad 0\le j\le r,
$$
form a <path in a graph> of length $r$. Consequently
$$
\boxed{d(A,B)=k-\dim(A\cap B).}
$$
Equal-distance ordered pairs have the same <dimensions> in this adapted <basis> construction. Extend both combined <bases> to <bases> of $V$, and match them by a <invertible linear map>. It maps the first ordered pair to the second and preserves <dimensions> of intersections, hence <graph adjacency>. \b[$GL_n(F)$ is <distance-transitive>], over an arbitrary <field>, with <graph diameter> $k$ under $n\ge2k$.
For the <symplectic dual polar graph>, <vertices> are Lagrangian $m$-spaces. Let $I=A\cap B$ have <dimension> $m-r$. The quotient $I^\perp/I$ is a nonsingular <symplectic vector space> of <dimension> $2r$, and $A/I,B/I$ are complementary <Lagrangian subspaces>. Their mutual pairing is nonsingular: a vector orthogonal to both lies in $(A+B)^\perp=I$, so vanishes in the quotient. Choose dual <bases> $e_1,\ldots,e_r$ in $A/I$ and $f_1,\ldots,f_r$ in $B/I$, and lift them into $A,B$. Their span is a nonsingular symplectic $2r$-space. Complete it by a <basis> $e_{r+1},\ldots,e_m$ of $I$ and suitable dual partners. This gives the pair normal form
$$
A=\langle e_1,\ldots,e_m\rangle,\qquad
B=\langle f_1,\ldots,f_r,e_{r+1},\ldots,e_m\rangle.
$$
The spaces $A_j=\langle f_1,\ldots,f_j,e_{j+1},\ldots,e_m\rangle$ remain <totally isotropic subspace>: a present $f_i$ pairs only with the absent $e_i$. They give an adjacent-step <path in a graph> of length $r$. The previous intersection-dimension lower bound still applies, proving
$$
\boxed{d(A,B)=m-\dim(A\cap B).}
$$
For two ordered pairs at the same distance, match their adapted <symplectic bases>. The resulting map preserves the <alternating bilinear form> and sends the pairs to each other, so lies in $Sp_{2m}(F)$. Equivalently, construct the <isometry of a space with a form> on $A+B$ from the displayed normal form and extend it by <Witt's lemma>. \b[The action of the <symplectic group over a field> is <distance-transitive>], over every <field>, and its graph has <graph diameter> $m$. The zero-dimensional boundary cases give a single <vertex> and trivial transitivity.
Back to article page
