How can we show Aut(J(v,k,i)) contains a subgroup isomorphic to sym(v), where v>k>i .

Question

This is Lemma 1.6.2 from the Book Algebraic Graph Theory by Chris Godsil and Gordon Royle. I tried proving this but not able to come up with a good proof, can some one please help me in doing this.

Answer 1

Let $X=J(v,k,i)$ be the graph whose vertices are the $k$-subsets of $\{1,2,\ldots,v\}$, and two vertices are adjacent in this graph whenever the cardinality of their intersection is exactly $i$. Observe that every permutation in $S_v$ also permutes the vertices of $X$, as follows: $g \in S_v$ takes vertex $\{ \alpha_1, \ldots, \alpha_k\}$ to vertex $\{ \alpha_1^g, \ldots, \alpha_k^g\}$. This induced permutation is an element in $Sym(V(X))$ and is an automorphism of $X$ because two vertices $A, B$ are adjacent in $X$ iff $|A \cap B| = i$ iff $|A^g \cap B^g|=i$. Here we used the fact that every permutation $g \in S_v$ preserves the cardinality of the intersection of two $k$-subsets, a fact which can be easily verified.

Hence, $S_v$ acts on $V(X)$ as a group of automorphisms of $X$. Also, this action is faithful because different permutations in $S_v$ effect different permutations in $Sym(V(X))$. Hence, there is an injective homomorphism from $S_v$ into the automorphism group $Aut(X)$, which implies that $S_v$ is isomorphic to a subgroup of $Aut(X)$.