4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you! I would also like to see if there is a simpler way. $\endgroup$ – Spencer Hyman Jan 1 '15 at 22:35
  • $\begingroup$ @Dongerz - There isn't! See my answer. $\endgroup$ – John Gowers Feb 12 '15 at 12:05
3
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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