3-arc-transitivity of the Odd graphs

203 Views Asked by At

The Kneser graph $K_s^{(r)}, (s \ge 2r+1)$ has as its vertex set the $r$-subsets of $\{1,2,\ldots,s\}$, with two vertices being adjacent iff the corresponding subsets are disjoint. An exercise asks to find the automorphism group of $K_s^{(r)}$, and then to "Deduce that the automorphism group of $K_{2r+1}^{(r)}$ is 3-arc-transitive," i.e. any path of length 3 can be mapped to any other path of length 3 by an automorphism. This exercise is from [Bollobas, Modern Graph Theory]. My question is about the "deduce" part, i.e. whether the first part of the exercise needs to be solved in order to solve the second part on 3-arc-transitivity.

More specifically, the automorphism group of $K_s^{(r)}$ can be shown to be $S_s$ (for example by using the Erdos-Ko-Rado theorem), and so the automorphism group $G$ of the so-called Odd graph $K_{2r+1}^{(r)}$ is $S_{2r+1}$. About the second part of the exercise, $G$ acts on the 3-arcs $\Omega$, where $|\Omega|=\frac{(2r+1)!}{(r-1)!(r-1)!}$, $|G|=(2r+1)!$. If I pick an arbitrary 3-arc $\alpha=(\alpha_0,\alpha_1,\alpha_2,\alpha_3)$, I can show that $|G_{\alpha}| = (r-1)!(r-1)!$, whence $|\alpha^G|$ is equal to $|\Omega|$. Thus $G$ is transitive on $\Omega$.

But I'm wondering whether we can prove 3-arc-transitivity as follows. Pick any 3-arc $\alpha$, and show that this choice of four vertices of $\alpha$ (i.e. the four subsets of $\{1,\ldots,s\}$) was made without loss of generality, i.e. any other 3-arc can be mapped to this 3-arc $\alpha$ by an automorphism of the graph induced by a permutation of $\{1,2,\ldots,s\}$. In other words, it seems to me that 3-arc-transitivity can be proved from the trivial observation that $S_{2r+1}$ is isomorphic to a subgroup of $G$, rather than from the more nontrivial result $S_{2r+1} \cong G$.

1

There are 1 best solutions below

0
On BEST ANSWER

You are correct. If a subgroup $G$ of the automorphism group of a graph $X$ acts 3-arc-transitively on $X$ then $X$ is 3-arc-transitive. You do not need to determine the full automorphism in this case.

In fact it would be unnatural since it takes the EKR theorem to get the full automorphism group, where all that is needed is the observation that $S_{2r+1}$ is acting nicely on the graph.