Automorphisms and enumeration of switching classes of tournaments

L. Babai ; P. J. Cameron

The electronic journal of combinatorics, Tome 7 (2000)

Résumé

Two tournaments $T_1$ and $T_2$ on the same vertex set $X$ are said to be switching equivalent if $X$ has a subset $Y$ such that $T_2$ arises from $T_1$ by switching all arcs between $Y$ and its complement $X\setminus Y$. The main result of this paper is a characterisation of the abstract finite groups which are full automorphism groups of switching classes of tournaments: they are those whose Sylow 2-subgroups are cyclic or dihedral. Moreover, if $G$ is such a group, then there is a switching class $C$, with Aut$(C)\cong G$, such that every subgroup of $G$ of odd order is the full automorphism group of some tournament in $C$. Unlike previous results of this type, we do not give an explicit construction, but only an existence proof. The proof follows as a special case of a result on the full automorphism group of random $G$-invariant digraphs selected from a certain class of probability distributions. We also show that a permutation group $G$, acting on a set $X$, is contained in the automorphism group of some switching class of tournaments with vertex set $X$ if and only if the Sylow 2-subgroups of $G$ are cyclic or dihedral and act semiregularly on $X$. Applying this result to individual permutations leads to an enumeration of switching classes, of switching classes admitting odd permutations, and of tournaments in a switching class. We conclude by remarking that both the class of switching classes of finite tournaments, and the class of "local orders" (that is, tournaments switching-equivalent to linear orders), give rise to countably infinite structures with interesting automorphism groups (by a theorem of Fraïssé).

Détail

DOI : 10.37236/1516

Classification : 05C25, 05E99, 20B25
Mots-clés : switching classes, tournaments, automorphism group