Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.