Automorphisms and enumeration of switching classes of tournaments

L. Babai*, P. J. Cameron

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)

Abstract

Two tournaments T1 and T2 on the same vertex set X are said to be switching equivalent if X has a subset Y such that T2 arises from T1 by switching all arcs between Y and its complement X \ 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) ≅ 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 ordersquot; (that is, tournaments switching-equivalent to linear orders), give rise to countably infinite structures with interesting automorphism groups (by a theorem of Fraissé).

Original languageEnglish
Pages (from-to)1-25
Number of pages25
JournalElectronic Journal of Combinatorics
Volume7
Issue number1 R
Publication statusPublished - 1 Dec 2000

Fingerprint

Dive into the research topics of 'Automorphisms and enumeration of switching classes of tournaments'. Together they form a unique fingerprint.

Cite this