Automorphism group of a tournament is solvable

Question

$(a)$ Let $X$ be a tournament, i.e. $X$ is a directed complete graph. Denote $V(X)$ the vertex set of $X$. An automorphism of $X$ is a bijection $V(X) \to V(X)$ preserving orientation. Prove that the automorphism group $\text{Aut}(X)$ is solvable.

$(b)$ Prove, in fact, that the following statements are equivalent:

Every group of odd order is solvable. $\iff$ $\text{Aut}(X)$ is solvable for every tournament $X$.

I am having trouble getting started, in particular how could I compute the automorphism group of a given tournament? This seems very hard if the number of vertices is large.

Answer 1

$(a)$ Let $X$ be a tournament on $n$ vertices, and $f\in \text{Aut}(X)$. Suppose $f$ has order $2$. Momentarily ignoring the orientation-preserving action of $f$, it is a permutation of $n$ letters, so we can decompose it into disjoint $2$-cycles and fixed points. Assume $f$ has a $2$-cycle, say $(ab)$. Without loss of generality, there is an arrow from $a$ to $b$. But there is also an arrow from $f(a) = b$ to $f(b) = a$, contradiction. Hence, $f$ is all fixed points: it is the identity. But then $f$ doesn't have order 2.

So Cauchy's Theorem tells us $\text{Aut}(X)$ must be odd. By the Feit-Thompson Theorem, $\text{Aut}(X)$ is solvable.

Answer 2

This question has already be answered by Sameer - the argument is essentially as follows:

If $X$ is a tournament, we show that the group $G=\operatorname{Aut}(X)$ has odd order. Otherwise, if it has even order then it must contain an element of order $2$, by Cauchy's theorem. But such an element must necessarily transpose two vertices, and hence reverse the arrow between them, meaning that it is not an automorphism of $X$. This is a contradiction, so $G$ must have odd order.

Now, by the Feit-Thompson Theorem, we conclude that $G$ is solvable.

This is a valid proof, but the Feit-Thompson theorem has a 200-page proof, and seems overpowered for this problem? Is there a simpler proof that avoids the Feit-Thompson Theorem?

The answer is - no there isn't! In fact, this problem is equivalent to the Feit-Thompson theorem thanks to a result of J. W. Moon stating that every group $G$ of odd order is the automorphism group of some tournament. Thus, if there were a simpler proof of this statement, it would immediately give a much simpler proof of the Feit-Thompson theorem:

• Let $G$ be a group of odd order. By Moon's result (which is much shorter to prove than FT), $G$ is the automorphism group of some tournament.
• By our putative simple proof, $G$ must be soluble.

Since no short proof of the Feit-Thompson Theorem is known, there is also no known short proof of this result that avoids the use of the Feit-Thompson Theorem.

If you found a short proof that the automorphism group of any tournament is soluble, it would be big news!