%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt]{article}
\setlength{\hsize}{152mm}
\setlength{\vsize}{217mm}
\usepackage{amsfonts}
\usepackage{latexsym}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{coroll}[theorem]{Corollary}
\newtheorem{premark}[theorem]{Remark}
\newenvironment{remark}{\begin{premark}\rm}{\end{premark}}
\newtheorem{pproblem}[theorem]{Problem}
\newenvironment{problem}{\begin{pproblem}\rm}{\end{pproblem}}
\newenvironment{proof}{\medbreak\noindent\textbf{Proof\ }}{\medbreak}
\newcommand{\normaleq}{\unlhd}
\newcommand{\Aut}{\mathop{\mathrm{Aut}}}
\newcommand{\Sym}{\mathop{\mathrm{Sym}}}
\newcommand{\orb}{\mathop{\mathrm{orb}}}
\newcommand{\res}{\mathop{\mathbf{res}}}
\newcommand{\cor}{\mathop{\mathbf{cor}}}
\newcommand{\odd}{\mathord{\mathrm{odd}}}
\newcommand{\Prob}{\mathop{\mathrm{Prob}}}
\newcommand{\qed}{\qquad$\Box$}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics \textbf{7} (2000),
\#R38\hfill}
\thispagestyle{empty}
\begin{document}
\title{Automorphisms and enumeration of switching classes of
tournaments}
\author{L. Babai and P. J. Cameron}
\date{}
\maketitle
\begin{center}
Department of Computer Science\\
University of Chicago\\
Chicago, IL 60637, U.\,S,\,A.\\
\small{\texttt{laci@cs.uchicago.edu}} \\
\bigskip
School of Mathematical Sciences\\
Queen Mary and Westfield College\\
%%Mile End Road\\
London E1 4NS, U.\,K.\\
\small{\texttt{P.J.Cameron@qmw.ac.uk}} \\
\end{center}
\begin{center}
Submitted: December 14, 1999; Accepted: August 1, 2000
\end{center}
\begin{abstract}
Two tournaments $T_1$ and $T_2$ on the same vertex set $X$ are said to be
\emph{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\"{\i}ss\'e).
\end{abstract}
\medskip\noindent
MR Subject Numbers: primary: 20B25; secondary: 05C25, 05C20, 05C30, 05E99
\begin{flushright}
{\large\em Dedicated to the memory of Paul Erd\H{o}s}
\end{flushright}
\section{Introduction}\label{intro}
The concept of \emph{switching} of graphs (sometimes referred to as
\emph{Seidel equivalence}) was first defined by
Seidel~\cite{seidel}. It is an equivalence relation under which
the labelled graphs on a set of $n$ vertices are partitioned
into equivalence classes of size $2^{n-1}$. Formulae for the
numbers of isomorphism types of switching classes, and of graphs
in a switching class, were found by Mallows and Sloane~\cite{ms}
and Goethals (personal communication), and are reported in \cite{pjc:cohom}.
It is also noted in \cite{pjc:cohom} that every
abstract group is the automorphism group of some switching class.
The purpose of this paper is to investigate a similarly-defined operation of
switching of tournaments, to characterise the automorphism groups of
switching classes, and to perform enumerations similar to those just
mentioned for graphs.
The operation of \emph{switching a graph} on the vertex set $X$ with
respect to a subset $Y$ of $X$ consists of complementing the adjacency
relation between $Y$ and the complementary set $X\setminus Y$
(that is, $y\in Y$ and $z\in X\setminus Y$ will be adjacent after switching
precisely if they were not adjacent before switching), and leaving
all other edges and non-edges unaltered.
Analogously,
the operation of \emph{switching a tournament} on the vertex set $X$ with
respect to a subset $Y$ of $X$ consists of reversing all the arcs between
$Y$ and the complementary set $X\setminus Y$, leaving all other arcs
unaltered.
Observe that in both contexts, switching with respect to $Y$ and to
$X\setminus Y$ are the same operation. In each case, the switching
operations form a group of order
$2^{n-1}$, where $n=|X|$. Switching equivalence partitions the set
of graphs and the set of tournaments on the vertex set $X$ into
equivalence classes of size $2^{n-1}$, called \emph{switching classes}
(of graphs and of tournaments, respectively).
Henceforth we shall discuss the case of tournaments only, except where
expressly stated otherwise.
A permutation $g$ of $X$ is said to be an \emph{automorphism} of the switching
class $C$ if it permutes among themselves the members of $C$. (Note that
here $g$ is an element of the symmetric group $\Sym(X)$, and is to be
distinguished from the induced permutation of $C$.) Clearly $g$
is an automorphism of $C$ if and only if it maps one member of $C$ into $C$.
In particular, the automorphism group of any tournament in $C$ is a subgroup
of the automorphism group of $C$. However, the containment may be proper.
For example, the automorphism group of any tournament has odd order, but
switching classes can admit automorphisms of even order.
In fact, the main result of this paper, proven in
Sections~\ref{group} and~\ref{rand}, asserts that {\em a finite abstract
group is the automorphism group of some switching class
of tournaments if and only if its Sylow 2-subgroups are cyclic
or dihedral} (Theorem~\ref{main1}).
The proof involves, in Section~\ref{rand}, a non-constructive
(probabilistic) technique which is of greater generality
than the particular result that we deduce from it.
We show that if $G$ is a semiregular permutation group
with a sufficiently large number of orbits and
$f$ is a random $G$-invariant digraph chosen from a rather
general class of probability distributions then with large
probability, $\Aut(f)=G$.
It is a simple corollary that, if $G$ has cyclic or dihedral Sylow
$2$-subgroups, then there is a switching class $C$,
with $\Aut(C)\cong G$, having the property that every subgroup
of $G$ of odd order is the full automorphism group of
a tournament in $C$ (Cor.~\ref{each-subgroup}).
We also show that a finite permutation group leaves some switching class
invariant if and only if its Sylow 2-subgroups are cyclic or dihedral and act
semiregularly (Theorem~\ref{perm}).
The enumeration results are given in Section~\ref{enume}, where
we count the tournaments in a switching class whose
automorphism group is given, and in Section~\ref{enume2},
where we count switching classes. The result in Section~\ref{enume}
generalises Brouwer's enumeration of local orders~\cite{brouwer}. We have
not been able to enumerate switching classes whose automorphism groups have
even order in general, but the number of such classes is found in the case
when $n$ is not divisible by $4$.
A consequence of the above enumerations is the existence of $(k-1)$-transitive
infinite permutation groups with exactly two orbits on $k$-sets and
two on $(k+1)$-sets for $k=3$ and $k=4$; these are relevant to the problem
considered in \cite{pjc:orbits} (see Section~\ref{homogen}).
\paragraph{Archaeology.}
Most of the results of this paper were proved in 1981-82. The manuscript
was subsequently lost as both authors moved. As a result of
a fortunate archaeological discovery, the paper came to light
again in 1993 at which time it was transfered to electronic media.
Further progress was made at a meeting hosted by the CRM, Montr\'eal
in September 1996. Finishing touches were put on the paper in 1999.
The main result, Theorem~\ref{main1}, has been cited
as ``Theorem 4.4(b)'' in~\cite[p.~1499]{lb:hbk}.
The most poignant moment of the story was that Saturday morning in
Montreal when, while working on what seemed to be the final version
of this paper, we learned from an e-mail message of the death of
Paul Erd\H{o}s. For a long while, we just stared at the screen
in disbelief. Occasionally, we still do.
\section{Equivalent objects: Switching classes, oriented two-graphs and
S-digraphs}\label{prelim}
%%We conclude this section by describing two objects ``equivalent'' to
In this section we describe two objects ``equivalent'' to switching
classes of tournaments, which we will need later.
We can regard a tournament as an antisymmetric function $f$ from ordered
pairs of distinct vertices to $\{\pm1\}$ (with $f(x,y)=+1$ if and only if
there is an arc from $x$ to $y$). Switching with respect to $\{x\}$ corresponds
to changing the sign of $f$ whenever $x$ is one of the arguments; and
switching with respect to an arbitrary subset is performed by switching with
respect to its singleton subsets successively. Given a tournament $f$,
define a function $g$ on ordered triples of distinct elements by the rule
\[g(x,y,z)=f(x,y)f(y,z)f(z,x).\]
Then $g$ is alternating (in the sense that interchanging two arguments changes
the sign) and satisfies the ``cocycle'' condition
\[g(x,y,z)g(y,x,w)g(z,y,w)g(x,z,w)=+1.\]
We call such a function an \emph{oriented two-graph}. Conversely, any
oriented two-graph arises from a tournament in this way. Switching the
tournament does not change the oriented two-graph, and in fact two
tournaments yield the same oriented two-graph if and only if they are
equivalent under switching. Thus there is a natural bijection between
switching classes of tournaments and oriented two-graphs; corresponding
objects have the same automorphism group.
A \emph{double cover} of a set $X$ is a set $\overline{X}$ with a surjective
map $p:\overline{X}\to X$ with the property that $|p^{-1}(x)|=2$ for all
$x\in X$. An \emph{S-digraph} $D$ on $\overline{X}$ is a digraph with
the properties
\begin{description}
\item{(a)} for all $x\in X$, the induced digraph on $p^{-1}(x)$ has no arcs;
\item{(b)} for all $x,y\in X$ with $x\not=y$, the induced digraph on
$p^{-1}(\{x,y\})$ is a directed 4-cycle.
\end{description}
It follows that, if $a,b\in \overline{X}$, then $a$ and $b$ are joined by an
arc if and only if $p(a)\not=p(b)$; and, if $p(a)=p(a')$ and $b$ is another
vertex, then the arcs on $\{a,b\}$ and $\{a',b\}$ are oppositely directed
at $b$.
Let $D$ be an S-digraph on $\overline{X}$. If the set $X_0$ contains one
vertex from each of the sets $p^{-1}(x)$ ($x\in X$), then $p$ induces a
bijection from $X_0$ to $X$, and the induced digraph on $X_0$ is mapped to
a tournament on $X$. Different choices of $X_0$ give rise to
switching-equivalent tournaments, and every tournament in the switching
class is realised in this way. Conversely, to each switching class, there
corresponds a unique S-digraph.
The S-digraph $D$ has an automorphism $z$ which interchanges the two
points of $p^{-1}(x)$ for all $x\in X$. Any automorphism of a switching
class lifts to two automorphisms of the S-digraph, differing by a
factor $z$. Thus, to a group $G\le \Aut(C)$
of automorphisms of the switching class $C$
corresponds a group $\overline{G}\le \Aut(D)$
of automorphisms of the S-digraph $D$,
with $\langle z\rangle\normaleq\overline{G}$ and
$\overline{G}/\langle z \rangle \cong G$.
(Thus $\overline{G}$ is an extension of the cyclic group of order 2 by $G$.)
We claim that {\em $z$ is the only involution} (element of order 2)
in $\Aut(D)$.
Indeed, let $t$ be any involution in $\Aut(D)$.
If $t$ interchanges vertices $a$ and $b$,
then $p(a)=p(b)$, since otherwise a directed arc would join $a$ and $b$ (by
the definition of an S-digraph). Moreover, $t$ cannot fix any further
vertex $c$, since the arcs on $\{a,c\}$ and $\{b,c\}$ are oppositely
directed.
It follows that $z$ is in the center of $\Aut(D)$ and the pairs
$\{a, za\}\ (a\in {\overline X})$ form a system of imprimitivity
for $\Aut(D)$. This in turn implies
that every automorphism of $D$ induces and automorphism
of $C$ and therefore $\Aut(D)/\langle z \rangle = \Aut(C)$.
We summarize our main conclusions.
\begin{prop} \label{extension-prop}
The automorphism group of the
S-digraph $D$ corresponding to the switching class $C$
contains a unique involution $z$ and $\Aut(D)/\langle z \rangle = \Aut(C)$.
Consequently, any group $G\le \Aut(C)$ acting on the
switching class $C$ is a quotient $G={\overline G}/\langle z \rangle$
where $z$ is the unique involution in the group $\overline G\le \Aut(D)$.
\end{prop}
This extension of $\Aut(C)$ and its subgroups
is crucial for our characterisation of the automorphism
groups of switching classes in Sections~\ref{group} and~\ref{rand}.
\section{Counting tournaments in a switching class}\label{enume}
In this section we give a formula for the number of non-isomorphic
tournaments in a switching class, in terms of the automorphism group of
the class. A particular case is the enumeration of locally transitive
tournaments, established using different methods by A. Brouwer~\cite{brouwer}.
\begin{lemma}
An automorphism of a switching class $C$ of tournaments
fixes some tournament in $C$ if and only if it has odd order.
\end{lemma}
\begin{proof}
Clearly an automorphism of a tournament has odd order.
Conversely, let $g$ be an automorphism of odd order of a switching class on
$n$ points. The group $T$ of switchings, of order $2^{n-1}$, acts regularly
on the switching class, and is normalised by $g$. By a simple special case
of the Schur--Zassenhaus theorem (\cite{hall}, p.~224),
$\langle g\rangle$ is conjugate (in $T\langle g\rangle$) to the
stabiliser of a tournament; that is, $g$ fixes a tournament.\qed
\end{proof}
\begin{theorem}
Let $G$ be the automorphism group of a switching
class $C$ of tournaments. Then the number of tournaments in $C$, up to
isomorphism, is
\[{1\over|G|}\sum_{{g\in G}\atop{|g|\;\odd}}2^{\orb(g)-1},\]
where $|g|$ is the order, and $\orb(g)$ the number of cycles, of $g$.
\end{theorem}
\begin{proof}
If $|g|$ is even, then $g$ fixes no tournament; if $|g|$ is odd, then
$g$ fixes one, and all the fixed tournaments are obtained by switching this
one with respect to fixed partitions, that is, with respect to fixed subsets,
since $g$ cannot interchange a subset with its complement. Now the
Orbit-Counting Lemma (the mis-attributed ``Burnside's Lemma'') gives the
result.\qed
\end{proof}
There is no ``trivial'' switching class of tournaments, invariant under the
symmetric group, if $|X|>2$. The simplest switching class is one whose
corresponding oriented two-graph is a \emph{circular order} (that is, can be
represented as a set of points on a circle so that $g(x,y,z)=+1$ if and only
if the points $x,y,z$ are in anticlockwise order).
A \emph{local order} (see~\cite{pjc:orbits}) is defined to
be a tournament containing no 4-vertex sub-tournament which consists of a
vertex dominating or dominated by a 3-cycle. Local orders also appear in
the literature under the names \emph{locally transitive tournaments}
\cite{lachlan} or \emph{vortex-free tournaments} \cite{knuth}.
\begin{lemma}
The following are equivalent for a switching class $C$
of tournaments:
\begin{description}
\item{(a)} $C$ contains a linear order;
\item{(b)} $C$ contains a local order;
\item{(c)} $C$ consists entirely of local orders;
\item{(d)} the corresponding oriented two-graph is a circular order.
\end{description}
\end{lemma}
\begin{proof}
An oriented two-graph is a circular order if and only if its restriction
to every 4-set is a circular order. Also, a tournament is a local order if
and only if its restriction to every 4-set is a local order. So the
equivalence of (b)--(d) can be shown by checking the result for
tournaments on 4 vertices.
Clearly (a) implies (b). The converse is proved by induction, being trivial
for switching classes on fewer than 4 vertices. So let $T$ be a local order
on $n$ vertices, assuming the result for fewer than $n$ vertices. Let $v$ be
any vertex. By the induction hypothesis, we can switch so that
$T\setminus\{v\}$ is a linear order, say $v_1<\cdotsi$, or the converses of these. In the first case, we have a linear order,
where $v$ comes between $v_i$ and $v_{i+1}$. In the second case, we obtain
a linear order by switching with respect to $\{v_1, \ldots, v_i\}$.\qed
\end{proof}
It follows from the equivalence of (a) and (d) that
there is a unique circular order on $n$ points (up to isomorphism). Its
automorphism group is the cyclic group of order $n$, acting regularly. This
group contains $\phi(n/d)$ elements of order $n/d$ for each $d$ dividing $n$,
such an element having $d$ cycles. Hence we obtain:
\begin{theorem}
The number of local orders on
$n$ points, up to isomorphism, is
\[{1\over n}\sum_{{d|n}\atop{n/d\;\odd}} 2^{d-1}\phi(n/d).\qquad\Box\]
\end{theorem}
This was first proved by Brouwer~\cite{brouwer} by means of
a correspondence with certain shift register sequences.
\begin{remark}
The number of non-isomorphic tournaments in a
switching class on $n$ vertices is at least $(3/2n)(2/\sqrt3)^n$. For if $G$
is the automorphism group of $C$, then the stabiliser $G_x$ fixes the unique
tournament in $C$ for which $x$ is a source, and so $|G_x|$ is odd. Thus
$|G_x|\le 3^{(n-2)/2}$ (Dixon~\cite{dixon}), and $|G|\le(n/3)3^{n/2}$. Since
$|C|=2^{n-1}$, $G$ has at least $(3/2n)(2/\sqrt3)^n$ orbits in $C$. (Note
that no such exponential bound holds for graphs: the switching class of the
null graph contains only $\lfloor n/2\rfloor+1$ non-isomorphic graphs.)
\end{remark}
\begin{remark}
Almost all switching classes of tournaments on $n$
points have all $2^{n-1}$ members pairwise non-isomorphic. This
is equivalent to Corollary~\ref{asymm} which states
that almost all switching classes have trivial automorphism groups.
\end{remark}
\section{Groups with a unique involution}
Our main results, Theorems~\ref{main1} and \ref{perm}, characterize
the automorphism groups of switching classes. Proposition \ref{extension-prop}
indicates the connection of these groups with groups containing a unique
involution. Therefore the following result is
a crucial ingredient in both proofs.
\begin{theorem} \label{cohomology}
For an abstract finite group $G$, the following are
equivalent:
\begin{description}
\item{(a)} $G$ has cyclic or dihedral Sylow $2$-subgroups;
\item{(b)} there exists a group $\overline{G}$ containing a unique
involution $z$ such that $\overline{G}/\langle z\rangle$ is isomorphic to $G$.
\end{description}
Moreover, the group $\overline G$ is uniquely determined by $G$.
\label{uniqinv}
\end{theorem}
This result is known
to some group theorists, but we are not aware of a proof in the literature.
We are indebted to G. Glauberman for the simple argument given here.
\begin{proof}
Suppose that (b) holds. Let $\overline{S}$ be a Sylow 2-subgroup of
$\overline{G}$, so that $S=\overline{S}/\langle z\rangle$ is a Sylow 2-subgroup
of $G$. Now $\overline{S}$ contains a unique involution, so it is
cyclic or generalised quaternion (Burnside~\cite{burnside}, p.~132),
and $S$ is cyclic or dihedral.
The reverse argument uses some facts about cohomology of groups, for which
we refer to Cartan and Eilenberg~\cite{ce}. Extensions of $\mathbb{Z}_2$ by
a group $G$ are described by elements of the cohomology group
$H^2(G, \mathbb{Z}_2)$. If $S$ is a cyclic or dihedral 2-group, then there
is an extension $\overline{S}$ of $\mathbb{Z}_2$ by $S$ containing a unique
involution, viz.\ a cyclic or generalised
quaternion group. Not only is such an extension unique up to isomorphism,
but it is readily checked that there is a unique cohomology class in
$H^2(S, \mathbb{Z}_2)$ corresponding to an extension with this property.
Let $t$ be a cohomology class for a subgroup $S$ of a group $G$. For any
$g\in G$, there is a corresponding class $t^g$ of the conjugate $S^g$. We
call $t$ \emph{stable} if the images of $t$ and $t^g$ under the restriction
maps $\res_{S,S\cap S^g}$ and $\res_{S^g,S\cap S^g}$ are equal for all
$g\in G$. If $S$ is a cyclic or dihedral 2-group, and $t$ the class defined
in the previous paragraph, the uniqueness of $t$ implies that it is stable
with respect to any supergroup $G$ of $S$.
A formula of Cartan and Eilenberg (\cite{ce}, p.~258) asserts that, if $t$ is
stable, then $\res_{G,S}\cor_{S,G}t=|G:S|t$, where $\cor_{S,G}$ denotes
the corestriction map. If $S$ is a Sylow 2-subgroup of $G$, then $|G:S|$ is
odd, and $2t=0$, since $t\in H^2(S, \mathbb{Z}_2)$. So the element
$t^*=\cor_{S,G}t$ of $H^2(G, \mathbb{Z}_2)$ satisfies $\res_{G,S}t^*=t$.
The extension $\overline{G}$ of $\mathbb{Z}_2$ by $G$ corresponding to $t^*$
has a unique element of order 2, since each of its Sylow 2-subgroups does.\qed
\end{proof}
\begin{remark}
The structure of groups satisfying the conditions
of the theorem is well known. Let $S_2(G)$ be the Sylow 2-subgroup
of $G$ and let $O(G)$ denote the largest normal subgroup of odd order
in $G$. If $S_2(G)$ is cyclic then $G=S_2(G)\cdot O(G)$ (semidirect
product, so $G/O(G)=S_2(G)$) by Burnside's transfer theorem
(\cite{burnside}, p.~155). The case when $S_2(G)$ is dihedral
is settled by the theorem of Gorenstein and Walter \cite{gw}:
\begin{quote}
\it Let $G$ be a group with dihedral Sylow $2$-subgroups.
Then $G/O(G)$ is isomorphic to $S_2(G)$ or to $A_7$ or
to a subgroup of
${\rm P}\Gamma{\rm L}(2,q)$ which contains ${\rm PSL}(2,q)$
(for $q$ odd).
\end{quote}
It is possible
to prove that (a) implies (b) in Theorem~\ref{uniqinv} using this
structural information in place of the cohomological argument, though
the proof is much longer.
\end{remark}
\begin{remark}
An interesting class of groups with a unique involution,
called ``binary polyhedral groups,''
is discussed by Coxeter (\cite{coxeter}, p.~82).
These groups are defined as the inverse images of the
usual polyhedral groups (groups of rotations of 3-dimensional polytopes)
under the 2-to-1 homomorphism from the 2-dimensional unitary group
over $\mathbb C$ to the 3-dimensional orthogonal group
over $\mathbb R$. Coxeter notes that the binary polyhedral
groups have a unique involution, notes that they share this property with
the groups $SL(2,q)$ ($q$ odd) and with the direct product
of any of these groups with a group of odd order. He goes on to
asking whether this is a complete list of groups with
a unique involution.
In a sense, the one-to-one correspondence given in
Theorem~\ref{uniqinv} settles this question. In particular,
groups $\overline G$ for which $O(G)$ is not a
direct factor in $G={\overline G}/\langle z\rangle$
are not covered by Coxeter's list.
It should be remarked, though, that the transition from
$G$ to $\overline G$ is not always immediate. For
instance, if $G=PSL(2,3)$ then ${\overline G}=SL(2,3)$,
as expected, but if $G=PGL(2,3)$ then ${\overline G}$
is the binary octahedral group (of order 48) which
is not isomorphic to $GL(2,3)$ (also of order 48)
even though $GL(2,3)$ has a unique central involution $z$
and $GL(2,3)/\langle z \rangle = PGL(2,3)$. (The trouble
is, $GL(2,3)$ has non-central involutions as well,
its Sylow 2-subgroup is dihedral.)
\end{remark}
\section{Automorphism groups of switching classes}\label{group}
In this section we begin the proofs of the following two theorems, which
characterise automorphism groups of switching classes of tournaments, and
the permutation groups which can act on switching classes.
We say that a switching class $C$ of tournaments on vertex set $X$
{\em admits} the permutation group $G \le \Sym(X)$ if $G\le \Aut(C)$.
\begin{theorem}
For a finite group $G$ of permutations of a finite
set $X$, the following are equivalent:
\begin{description}
\item{(a)} there is a switching class of tournaments on $X$ admitting $G$;
\item{(b)} $G$ has cyclic or dihedral Sylow $2$-subgroups which act
semiregularly on $X$.
\end{description}
\label{perm}
\end{theorem}
\begin{theorem} \label{main1}
For an abstract finite group $G$, the following are
equivalent:
\begin{description}
\item{(a)} $G$ is the full automorphism group of a switching class of
tournaments;
\item{(b)} $G$ has cyclic or dihedral Sylow $2$-subgroups.
\end{description}
\label{abs}
\end{theorem}
We first prove that, in each of Theorems~\ref{perm} and~\ref{abs},
condition (a) implies
condition (b). Suppose that the group $G$ acts on a switching class $C$ of
tournaments on $X$. Let $S$ be a Sylow 2-subgroup of $G$.
Combining Proposition~\ref{extension-prop} and Theorem~\ref{uniqinv}
we see that $S$ is cyclic or dihedral.
Next we examine the action of $S$ on $X$. Let $\overline{X}$ be a
double cover of $X$ carrying the S-digraph $D$ corresponding to
$C$. Let $\overline{G}$ be the extension of $\mathbb{Z}_2$ by $G$
acting on $D$ and inducing $G$ on $X$, as in
Proposition~\ref{extension-prop}.
Let $z$ denote the unique involution in $\overline G$.
Let $\overline{S}$ be a Sylow 2-subgroup of $\overline G$.
Then any non-identity subgroup of $\overline{S}$ contains $z$
and hence fixes no point. Thus $\overline{S}$
acts semiregularly on $\overline{X}$,
and so $S=\overline{S}/\langle z\rangle$ acts semiregularly on $X$.
\medbreak
The reverse implications in Theorems~\ref{perm}
and~\ref{abs} use similar constructions.
We consider Theorem~\ref{perm} first. Suppose that condition (b) holds. By
Theorem~\ref{uniqinv}, there
is a group $\overline{G}$ with unique involution $z$, such that
$\overline{G}/\langle z\rangle=G$. We construct a permutation
representation of $\overline{G}$ on a double cover $\overline{X}$ of $X$.
Take any orbit $Y$ of $G$ in $X$. For $y\in Y$, $G_y$ has
odd order, and so $\overline{G_y}$ has twice odd order. It follows that
$\overline{G_y}=\langle z\rangle\times H$, with $H\cong G_y$. So each
$\overline{G_y}$-coset in $\overline{G}$ is the union of two $H$-cosets, and
the coset space of $H$ in $\overline{G}$ is a double cover of the coset
space of $\overline{G_y}$, that is, of $Y$. The union of all such coset
spaces is thus a double cover $\overline{X}$ of $X$ on which $\overline{G}$
operates. Since $z\not\in H$, the element $z$ interchanges
the two points of $\overline{X}$ covering each point of $X$.
Furthermore, if $t\in\overline{G}$ has 2-power order and interchanges a pair of
points $a, b\in\overline{X}$, then $t=z$ and $p(a)=p(b)$. For $t^2$ fixes $a$
and $b$, and so the image of $t^2$ in $G$ is a 2-element with a fixed point,
and hence trivial; thus $t^2=1$ or $z$. The latter is impossible since $z$ is
fixed-point-free on $\overline{X}$. So $t^2=1$, whence $t=z$ and $p(a)=p(b)$.
It follows that all orbits of $\overline{G}$ on ordered pairs $(a,b)$ of points
of $\overline{X}$ with $p(a)\not=p(b)$ are antisymmetric. Moreover, if
$p(a)=p(a')$, then $(a,b)$ and $(a',b)$ lie in different orbits. It is thus
possible to select one orbit from each converse pair in such a way that, if
$p(a)=p(a')$ and $(a,b)$ is in a chosen orbit, then $(b,a')$ (rather than
$(a',b)$) is in a chosen orbit. Let $D$ be the digraph in which an arc goes
from $a$ to $b$ whenever $(a,b)$ lies in a chosen orbit. Then $D$ is a special
digraph admitting $\overline{G}$. As explained in Section~\ref{prelim}, it
follows that $G$ acts on a switching class of tournaments.
This proves Theorem~\ref{perm}.\qed
In the next section, we complete the proof of Theorem~\ref{abs}
by showing that, if $\overline G$ acts semiregularly with a large
number of orbits, then with high probability, a random
S-digraph constructed by the above procedure
has full automorphism group precisely $\overline{G}$.
\section[Automorphism groups of random $G$-invariant digraphs]%
{Automorphism groups of random\hfil\break $G$-invariant digraphs}\label{rand}
%%Throughout this section, we use a convention different from that of
%%Section~\ref{prelim}:
We shall regard a \emph{digraph} as a
function $f$ from ordered pairs of distinct vertices to
$\{\pm1\}$ with $f(x,y)=+1$ if there is an arc from $x$ to $y$.
A graph corresponds to a symmetric function. (Note that
for S-digraphs, $f$ is neither symmetric nor antisymmetric.)
If the function $f$ is a random variable,
we obtain the notion of a \emph{random digraph}.
We allow $f$ to have an arbitrary, $(n^2-n)$-dimensional $\pm1$
distribution. In particular, the projections $f(x,y)$ and $f(x',y')$ do not
have to be independent even if $\{x,y\}\cap\{x',y'\}=\emptyset$.
We shall need a fairly general lemma which is useful in various situations
in which our digraphs are picked at random from a collection of digraphs
admitting a given permutation group with small orbits.
Our model is the following. The vertex set $X$ will be partitioned into
(non-empty) classes $X_1, \ldots, X_m$. A set of pairs $\{(x_1,y_1),\ldots,
(x_s,y_s)\}$ will be called $(X_1, \ldots, X_m)$-\emph{independent}, if
\begin{description}
\item{(a)} no $\{x_i,y_i\}$ is a subset of any $X_k$;
\item{(b)} no $\{x_i,y_i,x_j,y_j\}$ is a subset of any $X_k\cup X_l$ for
any $i\not=j$, $1\le i,j\le s$, $1\le k,l\le m$.
\end{description}
Clearly, $s\le{m\choose 2}$ in this case. We shall say that the random
digraph $f$ is \emph{uniformly distributed} between $(X_1, \ldots, X_m)$ if
\begin{description}
\item{(A)} $\Prob(f(x,y)=1)={1\over2}$ whenever $x$ and $y$ belong to
different classes;
\item{(B)} for any $(X_1, \ldots, X_m)$-independent set $\{(x_1, y_1), \ldots,
(x_s, y_s)\}$, the random variables $f(x_i,y_i)$ (for $i=1, \ldots, s$) are
totally independent.
\end{description}
\begin{lemma}
Let the $n$-element set $X$ be partitioned as
$X=X_1\cup\ldots\cup X_m$ into pairwise disjoint classes of bounded size:
$|X_i|\le t$ for some fixed $t$. Let $f$ be a random digraph, uniformly
distributed between $(X_1,\ldots, X_m)$. Then the probability of the
event that all but at most $m^{1/2+\epsilon}$ of the $X_i$ are invariant
under $\Aut(f)$ is greater than $1-\epsilon$ for any positive $\epsilon$
provided that $n>n_0(t,\epsilon)$.
\label{4ml}
\end{lemma}
\begin{proof}
We say that a permutation $\alpha\in\Sym(X)$ \emph{destroys} a set
$A\subseteq X$ if $A$ is not invariant under $\alpha$. Let $r(\alpha)$
denote the number of classes destroyed by $\alpha$.
For some $\alpha\in\Sym(X)$, let $x_1, \ldots, x_k$ be a maximal subset of
$X$ such that all the $2k$ elements $x_1, \ldots, x_k, \alpha x_1,
\ldots, \alpha x_k$ belong to different classes.
We claim that $k\ge r/(2t+1)$, where $r=r(\alpha)$.
Indeed, let $X_1,\ldots,X_r$ be the classes destroyed by $\alpha.$
For each $i\le r$, pick a point $z_i\in X_i$ such that
$\alpha z_i \not\in X_i.$ Now define
a graph on the vertex set $\{1,\ldots,r\}$ by joining $i$ and $j$ if
the pair $\{z_i, \alpha z_i\}$ is in conflict with the pair
$\{z_j, \alpha z_j\}$ (conflict meaning that some class $X_{\ell}$ meets
both pairs). Since by assumption all $X_i$ have size $\le t,$
the vertices of the graph constructed have degree $\le 2t.$
Therefore the chromatic number of the graph is at most $2t+1,$
hence it has an independent set of size $\ge r/(2t+1),$
establishing the Claim.
Now the set of $k(k-1)$ pairs $\{(x_i,x_j),
(\alpha x_i,\alpha x_j) : 1\le in_0(t,\epsilon)$. Having thus estimated
the maximum number of classes destroyed by individual automorphisms of $f$,
we only need the following observation to establish the stated bound on the
total number of classes destroyed by $\Aut(f)$.
\end{proof}
\begin{prop}
Let $G$ be a finite group acting on a set $X$. Let
$A_1, \ldots, A_s$ be subsets of $X$ which are not invariant under $G$.
Then there exists $\alpha\in G$ which destroys at least half the classes $A_i$.
\label{4killhalf}
\end{prop}
\begin{proof}
We use the simple trick sometimes known as the ``first moment method''
(see~\cite{es}, p.~5). Let $\alpha$ be a random member of $G$ (each element
of $G$ having the same chance to be $\alpha$). For each $i$, the probability
that $A_i$ is invariant under $\alpha$ is at most $1/2$ (since the setwise
stabiliser in $G$ of $A_i$ is a proper subgroup). Hence the expected
number of those $A_i$ destroyed by $\alpha$ is at least $s/2$.\qed
\end{proof}
Now, an application of Proposition~\ref{4killhalf} with those $X_i$
not invariant under $G=\Aut(f)$ playing the roles of
$A_1, \ldots, A_s$ completes the proof of Lemma~\ref{4ml}.\qed
Next, we turn our attention to random digraphs invariant under a permutation
group action.
\medbreak
Let $G$ be a group acting on $X$, the vertex set of the random digraph $f$.
We shall say that the random variable $f$ is $G$-\emph{invariant} if
$\Prob(G\le\Aut(f))=1$; in other words, $\Prob(f(x,y)=f(gx,gy))=1$ for all
$g\in G$, $x,y\in X$.
We shall need the following stronger version of condition (B):
\begin{description}
\item{(B$'$)} If $(i_1,j_1),\ldots, (i_s,j_s)$ are distinct pairs of numbers
from $\{1, \ldots, m\}$ such that $(i_h,j_h)\not=(j_k,i_k)$ ($k,h=1, \ldots,
s$), then the projections $f|X_{i_h}\times X_{j_h}$ ($h=1, \ldots, s$) are
totally independent.
\end{description}
We shall say that $f$ is \emph{strongly uniformly distributed between}
$(X_1, \ldots, X_m)$ if (A) and (B$'$) hold.
\begin{theorem}
Let $G$ be a group of order $t$ acting semiregularly
on the set $X$, with orbits $X_1, \ldots, X_m$. Let $f$ be a random
$G$-invariant digraph on $X$, strongly uniformly distributed between
$(X_1, \ldots, X_m)$ and satisfying the additional condition (C) below. Then
$\Prob(\Aut(f)=G)>1-\epsilon$ for any positive $\epsilon$ provided that
$|X|=n>n_0(t,\epsilon)$.
\label{probthm}
\end{theorem}
\begin{description}
\item{(C)} For any $i\not=j$ and any $x,x'\in X_i$ and $y,y'\in X_j$,
\[\Prob(f(x,y)=f(x',y'))\le1/2.\]
\end{description}
\begin{proof}
By Lemma~\ref{4ml}, with probability greater than $1-\epsilon$,
most orbits of $G$ are invariant under $\Aut(f)$
Let us first consider permutations $\alpha\in\Sym(X)$ under which all the
$X_i$ are invariant.
We select representatives $x_i\in X_i$ for $i=1,\ldots, m$. Let $E_k$
denote the event
that there exists $\alpha\in\Aut(X)\setminus G$ which preserves the classes
$X_i$ and fixes precisely $k$ of $x_1, \ldots, x_m$. The probability that,
for some $i>k$, the vertex $x_i$ ``has a place to go'' while $x_1, \ldots,
x_k$ are fixed is at most $(t-1)2^{-k}$, since the ``place'' must be some
$y\in X_i$ with $y\not=x_i$, and
\[\Prob(f(x_i,x_j)=f(y,x_j)\hbox{ for all }j=1, \ldots, k)\le 2^{-k}.\]
(We used (C) (employing semiregularity) and (B$'$) here.) Using (B$'$)
again, we find that the probability that $x_{k+1}, \ldots, x_m$ all have
places to go while $x_1, \ldots, x_k$ are fixed is not greater than
$((t-1)2^{-k})^{m-k}$. Finally,
\begin{equation}
\Prob(E_k)\le{m\choose k}((t-1)2^{-k})^{m-k}.
\label{eq1}
\end{equation}
Our next observation is that any $\alpha\in\Sym(X)$ which preserves the $X_i$
agrees with some $g\in G$ in at least $m/t$ of the $x_i$. (Again, we use the
``first moment method'': pick a random $g\in G$; then the expected number
of those $x_i$ such that $\alpha x_i=gx_i$ is exactly $m/t$.) Now
$g^{-1}\alpha$ fixes $k\ge m/t$ of the $x_i$.
Hence the probability of the event
$A$ that there exists an $\alpha\in\Aut(f)\setminus G$ which preserves the
$X_i$ is
\begin{equation}
\Prob(A)\le\sum_{k=k_0}^m\Prob(E_k),
\label{eq2}
\end{equation}
where $k_0=\lceil m/t\rceil$.
As above, the probability that any particular member of $X_1$
has a place to go while
$x_1, \ldots, x_m$ are fixed is less than $(t-1)2^{-m+1}$. Consequently,
\begin{equation}
\Prob(E_m)\le n(t-1)2^{-m+1}.
\label{eq3}
\end{equation}
Combining (\ref{eq1}), (\ref{eq2}) and (\ref{eq3}),
we obtain for large enough $n$ (meaning
$n>2t^2\log_2t$, and therefore $t<2^{m/2t}$):
\begin{eqnarray*}
\Prob(A) &\le& \sum_{k=k_0}^m\Prob(E_k)\\
&\le& n(t-1)2^{-m+1}+\sum_{k=k_0}^{m-1}{m\choose k}((t-1)2^{-k})^{m-k}\\
&<& 2nt2^{-m}+\sum_{k=1}^{m-1}{m\choose k}2^{-k(m-k)/2}\\
&<& 2nt2^{-m}+2\sum_{k=1}^m{m\choose k}2^{-km/4}\\
&=& 2nt2^{-m}+2((1+2^{-m/4})^m-1)\\
&<& 3m2^{-m/4};
\end{eqnarray*}
hence
\begin{equation}
\Prob(A)<3m2^{-m/4}.
\label{eq4}
\end{equation}
Now we turn to those automorphisms of $f$ which destroy some of the
orbits of $G$. The number of orbits destroyed is negligible, by
Lemma~\ref{4ml}:
it is less than $m^{2/3}$, say, with probability greater than $1-\epsilon$,
provided that $n>n_0(t,\epsilon)$.
Set $q=\lfloor m^{2/3}\rfloor$. Let us consider those $\alpha\in\Sym(X)$
which preserve the sets $X_1, \ldots, X_{m-q}$.
Restricting the above result to the subgraph induced by the set
$Y=X_1\cup\ldots\cup X_{m-q}$, we find that the probability
of the existence of such an $\alpha\in\Aut(f)$ whose
restriction to $Y$ is not a member of the restriction
of $G$ to $Y$, is less than
\begin{equation}
3(m-q)2^{-(m-q)/4} < 2^{-m/5}
\label{eq5}
\end{equation}
(for large $m$).
Suppose now that $\alpha|Y=g|Y$ for some $g\in G$. Now $g^{-1}\alpha|Y$ is the
identity. We estimate the probability that some $x\in X\setminus Y$ can
still move. Let $y\in X\setminus Y$, $x\not=y$, and let $x_1, \ldots,
x_{m-q}$ be representatives of $X_1, \ldots, X_{m-q}$, respectively. We
claim that
\begin{equation}
\Prob(f(x,x_j)=f(y,x_j)\hbox{ for }j=1, \ldots, m-q)\le2^{-m+q}.
\label{eq6}
\end{equation}
If $y$ belongs to the $G$-orbit of $X$ then (\ref{eq6}) follows from (C) (by
semiregularity) and (B$'$). If $y$ does not belong to $Gx$ then (\ref{eq6})
simply follows from (A) and (B) (and we have equality in this case).
Consequently, the probability that there exists $\alpha\in\Aut(f)\setminus G$
preserving $X_1, \ldots, X_{m-q}$ is less than
\begin{equation}
2^{-m/5}+{qt\choose2}2^{-m+q} < 2^{-m/6}.
\label{eq7}
\end{equation}
Finally,
\begin{eqnarray*}
\Prob(\Aut(f)\not=G) &=& \Prob(\Aut(f)\not\le G)\\
&\le& \Prob(\Aut(f)\hbox{ destroys more than $q$ orbits of $G$})\\
&& \qquad +{m\choose q}2^{-m/6}\\
&<& \epsilon+m^q2^{-m/6}\\
&<& 2\epsilon
\end{eqnarray*}
for $n>n_0'(t,\epsilon)$.\qed
\end{proof}
\begin{remark} \label{little-oh}
Theorem~\ref{probthm} remains valid (with the same proof) if
$G$ acts regularly on all but $o(m)$ orbits and arbitrarily on the remaining
small fraction of the set of orbits.
\end{remark}
We are now ready to derive the reverse implication in Theorem~\ref{abs}
from Theorems~\ref{uniqinv} and~\ref{probthm}.
Let $G$ be a finite group with cyclic or dihedral Sylow 2-subgroups. By
Theorem~\ref{uniqinv}, there exists a group $\overline{G}$ containing
a single involution $z$ such that $G\cong\overline{G}/\langle z\rangle$.
Let $t=|\overline{G}|$. Let $\overline{G}$ act semiregularly with orbits
$X_1, \ldots, X_m$ on a set $\overline{X}$ of size $n=mt$ for some large
number $m$. Let us define the double cover $p:\overline{X}\to X$ by
contracting every orbit of $\langle z\rangle$. It is this map
$p$ with respect to which we shall use the term
``S-digraph'' (cf.~Section~\ref{prelim}).
We are going to define \emph{random $\overline{G}$-invariant S-digraphs}
on $\overline{X}$ with respect to $p$. Being special, no arcs join any pair
$x,zx$ for $x\in\overline{X}$, and for all distinct $x,y\in\overline{X}$,
the subgraph induced by
$\{x,y,zx,zy\}$ is an oriented 4-cycle. {From} each $\overline G$-orbit of
these
4-tuples we select one and decide by independent flips of a fair coin
which way the 4-cycle should be oriented. We transfer the orientation to
the other 4-cycles of this form by the action of $\overline{G}$.
Clearly the resulting random digraph $f$ satisfies (A), (B$'$) and (C).
Therefore, by Theorem~\ref{probthm}, we have
$\Prob(\Aut(f)=\overline{G})>0$ for $m>m_0(t)$. This
proves the existence of an S-digraph with automorphism group
$\overline{G}$, and hence the existence of a switching class of tournaments
with automorphism group $G$ (cf.\ Section~\ref{prelim}).\qed
\medbreak
Applying this argument to the trivial group ($|G|=1$) we obtain
the following corollary. An object is \emph{asymmetric} if its
automorphism group is trivial.
\begin{coroll} \label{asymm}
Almost all switching classes of tournaments are asymmetric.
The same holds for switching classes of graphs.\qed
\end{coroll}
Corollary~\ref{asymm} strengthens the well-known results that almost all
labelled graphs (tournaments) are asymmetric~(\cite{er}).
\begin{remark}
Similarly, one can derive from Theorem~\ref{probthm} that
the full automorphism group of a $G$-invariant random graph, digraph or
tournament almost always coincides with $G$, provided that $G$ acts
semiregularly with a large number of orbits.
\end{remark}
In particular, these statements prove the existence of
graphs, digraphs, tournaments
with prescribed abstract groups $G$ as their full automorphism groups
(with $|G|$ odd in the case of tournaments). The existence of such objects
can, however, be proved quite easily by direct constructions (cf.\ e.g.
\cite{lovasz}, Chapter~12, Problems 5, 6, 7). Moreover, direct constructions
yield such objects with only one or two $G$-orbits. (These results are
discussed in the surveys~\cite{lb:survey} and \cite{bg:survey}.)
The above
proof of Theorem~\ref{abs} appears to be the first case where the existence
of an object with prescribed abstract group of automorphisms has been
demonstrated without actually constructing such an object. We were not able
to find any elegant construction. A problem of interest in this direction
is the following.
\begin{problem}
Given a group $G$ with cyclic or dihedral Sylow $2$-subgroups, does there
exist a switching class of tournaments whose full automorphism group is
isomorphic to $G$, and $G$ acts with a bounded number of orbits
on the set of vertices? (The bound should be an absolute constant.)
\end{problem}
The problem of restricting the automorphism groups of a $G$-invariant
random graph, where $G$ is semiregular with a small number of orbits, seems
quite difficult (cf. \cite{b-godsil}).
\begin{remark}
%%***By the remark following the proof of Theorem~\ref{uniqinv},
By Remark~\ref{little-oh}
it follows that any permutation group, whose Sylow 2-subgroups are cyclic
or dihedral and act semiregularly, actually occurs as a section of the
full automorphism group of a switching class of tournaments (that is,
the restriction to an invariant subset).
\end{remark}
\medskip
The following observation leads to a further important corollary.
\begin{prop}
If $\overline{G}$ is a semiregular permutation group
with two or more orbits, and if $\overline{G}=\Aut(f)$ for some S-digraph
$f$, then every subgroup $H$ of $G=\overline{G}/\langle z\rangle$ of odd order
occurs as the automorphism group of some member of the corresponding
switching class. (Here $z$ denotes the unique involution in $\overline{G}$.)
\end{prop}
\begin{proof}
Let $\overline{H}$ be the preimage of $H$ in $G$, so $z\in\overline{H}$ and
$\overline{H}/\langle z\rangle=H$. Let $K$ be the (unique) index-2 subgroup of
$\overline{H}$; so $\overline{H}= K\times\langle z\rangle$, and $K\cong H$.
Within each $\overline{G}$-orbit, select a ``root.'' Making $g\in\overline{G}$
correspond to the $g$-image of the root establishes a bijection
between $\overline{G}$ and the orbit.
Within one $\overline{G}$-orbit, select one of each pair of
$K$-orbits interchanged by $z$; make a corresponding
selection (under the bijections discussed)
in every $\overline{G}$-orbit except one, where
one choice is made differently. The required tournament
is induced on the chosen set of vertices. \qed
\end{proof}
Hence we have the following corollary:
\begin{coroll} \label{each-subgroup}
Given a finite group $G$ with cyclic or dihedral
Sylow $2$-subgroups, there exists a switching class of tournaments with
$G$ as its full automorphism group, with the property that every subgroup of
$G$ with odd order occurs as the full automorphism group of some tournament
in this switching class.\qed
\end{coroll}
This answers a question of the second author~\cite[p.~118]{pjc:survey}.
\section{Counting switching classes}\label{enume2}
The following specialisation of Theorem~\ref{perm} is crucial to the
enumeration of
switching classes of tournaments. Call a permutation \emph{level} if the
powers of 2 dividing its cycle lengths are all equal. Note that a
permutation on an odd number of points is level if and only if it has odd
order. Let $L_n$ be the set of level permutations in the symmetric group
$S_n$.
\begin{lemma}
A permutation leaves invariant some switching class of
tournaments if and only if it is level.
\end{lemma}
\begin{proof}This is immediate from Theorem~\ref{perm}
applied to the cyclic group generated by the permutation.\qed
\end{proof}
Now let $A$ be the group of order $2^{n(n-1)/2}$ whose elements are the
operations of reversing prescribed sets of arcs in tournaments on $X$, where
$|X|=n$. Then $A$ permutes regularly the (labelled) tournaments on $X$; and
the group $T$ of switchings is a subgroup of $A$ whose orbits are the
switching classes. So $B=A/T$ permutes regularly the switching classes.
Thus, if a permutation $g$ fixes a switching class, then the number of
switching classes it fixes is equal to the number of elements of $B$ that
it fixes. This number is easily computed, and in any case is known from
the enumeration of switching classes of graphs by Mallows and
Sloane~\cite{ms}: it is
\[2^{\orb_2(g)-\orb(g)+\delta(g)},\]
where $\orb_2(g)$ is the number of orbits of $\langle g\rangle$ on
unordered pairs,
and $\delta(g)$ is 0 if all cycles of $g$ have even length, or 1 otherwise.
(So, if $g$ is level, then $\delta(g)=1$ or 0 according as $|g|$ is odd
or even.) Thus we obtain:
\begin{theorem}
The number of switching classes of tournaments on
$n$ vertices, up to isomorphism, is
\[{1\over n!}\sum_{g\in L_n}2^{\orb_2(g)-\orb(g)+\delta(g)}.\qquad\Box\]
\end{theorem}
For small values of $n$, we obtain the following.
\begin{center}
\begin{tabular}{|c|r|r|r|r|r|r|r|}
\hline
$n$ & 2 & 3 & 4 & 5 & 6 & 7 & 8\\
\hline
switching classes & 1 & 1 & 2 & 2 & 6 & 12 & 79\\
\hline
\end{tabular}
\end{center}
\begin{remark}
The number of switching classes of tournaments
is smaller than the number of switching classes of graphs if $n\ge 3$. For
the formula is a sum of some of the terms appearing in the sum found by
Mallows and Sloane, viz.\ those for which the permutation is level; and if
$n\ge3$, then not every permutation is level.
\end{remark}
\begin{remark}
A striking difference between the enumeration
problems for graphs and tournaments is that every automorphism of a
switching class of graphs fixes some graph in that class~\cite{ms}. It
would be interesting to enumerate the switching classes of tournaments
for which this fails, that is, those whose automorphism groups have even
order. We cannot do this, but the following results give the answer in
some cases.
\end{remark}
\begin{lemma}
Let $G$ be a group acting on a set $X$, and $H$ a
normal subgroup of $G$ of prime index. Then the number of orbits of $G$
on $X$ consisting of points whose stabilisers contain elements of $G\setminus
H$ is
\[{1\over|G\setminus H|}\sum_{g\in G\setminus H}\pi(g),\]
where $\pi(g)$ is the number of fixed points of $g$ in $X$.
\label{odd}
\end{lemma}
\begin{proof}
The standard proof of the Orbit-Counting Lemma shows that
\[\sum_{g\in G}\pi(g)=\sum_{x\in X}|G_x|,\]
and that the right-hand expression is
$|G|$ times the number of orbits. Let $Y$ be the set $\{y:(G\setminus H)\cap
G_y\not=\emptyset\}$. Clearly $\sum_{g\in G\setminus H}\pi(g)$ is equal to
$\sum_{y\in Y} |(G\setminus H)\cap G_y|$, which in turn is
$((p-1)/p)\sum_{y\in Y}|G_y|$, where $p=|G:H|$, since $|G_y:G_y\cap H|=p$.
Thus the sum is
\[{p-1\over p}|G|\#\orb(G,Y) = |G\setminus H|\#\orb(G,Y).\qquad\Box\]
\end{proof}
\begin{prop}
The number of switching classes of tournaments on
$n$ vertices admitting odd permutations is
\[{2\over n!}\sum_{g\in L_n\cap(S_n\setminus A_n)} 2^{\orb_2(g)-\orb(g)}.\]
\end{prop}
\begin{proof}
Observe that if $g\not\in A_n$ then $g$ has even order, so $\delta(g)=0$
for all $g\in L_n\cap(S_n\setminus A_n)$. Apply Lemma~\ref{odd}.\qed
\end{proof}
\begin{coroll}
If $n\equiv2\!\!\pmod4$, then the number of
switching classes of tournaments on $n$ vertices whose automorphism groups
have even order is
\[{2\over n!}\sum_{{g\in L_n}\atop{|g|\;\rm{even}}} 2^{\orb_2(g)-\orb(g)}.\]
\end{coroll}
\begin{proof}
If $n\equiv2\!\!\pmod4$, a level permutation is odd if and only if its
order is even.\qed
\end{proof}
\begin{remark}
This formula is trivially valid also for $n$ odd,
and holds as well if $n=4$.
\end{remark}
\begin{coroll}
If $n$ is a power of $2$, there are $2^{n/2}/n$
cyclic switching classes of tournaments on $n$ vertices.
\label{poweroftwo}
\end{coroll}
\begin{proof}
If $n$ is a power of 2, the only odd level permutations are $n$-cycles;
there are $(n-1)!$ of these, and if $g$ is one of them, then $\orb_2(g)=n/2$,
$\orb(g)=1$.\qed
\end{proof}
There is an alternative direct proof. An $n$-cycle $g$ fixes
$2^{n/2-1}$ switching classes. If $C$ is one of these, then
$\langle g\rangle$ is a Sylow 2-subgroup of $G=\Aut(C)$. By
Burnside's transfer theorem, $G$ has a normal 2-complement $N$;
and $N=1$, since $N$ has odd order and acts $1\over2$-transitively
on a set of 2-power size. So $G=\langle g\rangle$. Thus, if two
$g$-invariant switching classes are isomorphic, then the
isomorphism between them normalises $\langle g\rangle$. Since
$N(\langle g\rangle)/\langle g\rangle$ has order $n/2$, the number
of isomorphism classes is $2^{n/2-1}/(n/2)$.
\begin{remark}
The number in Corollary~\ref{poweroftwo}
is equal to the number of local orders on $n/2$ points.
\end{remark}
\section{Application: homogeneous models and infinite permutation groups}
\label{homogen}
We conclude the paper with the descriptions of two infinite permutation
groups relevant to a problem discussed in~\cite{pjc:orbits}. The
discussion here will be brief; more detail on the background can
be found in~\cite{pjc:oligo}.
A class $\mathcal{C}$ of structures is said to be \emph{hereditary} if
it is closed under taking induced substructures on subsets. It has
the \emph{amalgamation property} if, whenever $f_i:A\to B_i$ are
embeddings of structures in $\mathcal{C}$ for $i=1,2$, then there exist
embeddings $g_i:B_i\to C$, for some structure $C$ in $\mathcal{C}$,
such that $f_1g_1=f_2g_2$.
It follows from a model-theoretic construction due to
Fra\"{\i}ss\'e~\cite{fraisse} that, if the finite models of
a first-order theory in a relational language are
hereditary and have the amalgamation property, then there is a unique
countable homogeneous model containing all finite models as
substructures. (Here we say that a structure is \emph{homogeneous} if
any isomorphism between finite induced substructures can be extended
to an automorphism of the structure.) In
this situation, if $G$ denotes the automorphism group of this model, then
the number $n_k(G)$ of $G$-orbits on $k$-sets is equal to the number of
$k$-element models (up to isomorphism).
It is easily verified that both local orders and oriented two-graphs have
the hereditary and amalgamation properties. The number of local orders on
2, 3, 4 points are 1, 2, 2 respectively. So, if $G_1$ is the automorphism
group of the homogeneous local order, then $G_1$ is 2-homogeneous and
satisfies $n_3(G_1)=n_4(G_1)=2$. Similarly, if $G_2$ is the automorphism
group of the homogeneous oriented two-graph, then $G_2$ is 3-homogeneous
and satisfies $n_4(G_2)=n_5(G_2)=2$. These are two of a very short list of
known primitive infinite permutation groups $G$ with $n_k(G)=n_{k+1}(G)>1$
for some $k$ (see~\cite{pjc:orbits}, IV).
\medbreak
Lachlan~\cite{lachlan} determined all countable homogeneous tournaments
(see also Cherlin~\cite{cherlin}). There are just three of them: the
transitive tournament $\mathbb{Q}$, the homogeneous local order considered
above, and the homogeneous tournament $T$ containing all finite
tournaments. The homogeneous oriented two-graph mentioned above
corresponds to the switching class of $T$.
The orbit-counting sequences associated with these two examples
appear as numbers A000016 and A049313 in the \textit{On-Line Encyclopedia of
Integer Sequences}~\cite{eis}. The second author is currently
compiling a list of sequences which count group orbits on
$k$-tupes in this way~\cite{pjc:list}.
\begin{thebibliography}{99}
\bibitem{lb:two}
L. Babai, On the minimum order of graphs with given group,
\textit{Canad. Math. Bull.} \textbf{17} (1974), 467--470.
\bibitem{lb:survey}
L. Babai, On the abstract group of automorphisms,
in \textit{Combinatorics} (ed. H. N. V. Temperley),
London Math. Soc. Lecture Notes \textbf{52}, Cambridge University Press, 1981,
pp.~1--40.
\bibitem{lb:hbk}
L. Babai, Automorphism groups, isomorphism, reconstruction,
in \textit{Handbook of Combinatorics} (ed. R.~L.~Graham,
M.~Gr\"otschel and L.~Lov\'asz), North-Holland, Amsterdam, 1995,
pp.~1447--1540.
\bibitem{b-godsil}
L. Babai and C. D. Godsil,
On the automorphism groups of almost all Cayley graphs,
\textit{Europ. J. Combinatorics} \textbf{3} (1982), 9-15.
\bibitem{bg:survey}
L. Babai and A. J. Goodman,
On the abstract group of automorphisms,
in \textit{Coding Theory, Design Theory, Group Theory}
(ed. D. Jungnickel and S. A. Vanstone),
Wiley, New York, 1993, pp.~121--143.
\bibitem{brouwer}
A. Brouwer, The enumeration of locally transitive tournaments,
\textit{Afd. Zuiv. Wisk.} \textbf{138}, Math. Centrum, Amsterdam, 1980.
\bibitem{burnside}
W. Burnside, \textit{Theory of Groups of Finite Order},
2nd edition, Cambridge University Press, 1911, reprinted
Dover Publications, New York, 1955.
\bibitem{pjc:cohom}
P. J. Cameron, Cohomological aspects of two-graphs, \textit{Math. Z.}
\textbf{157} (1977), 101--119.
\bibitem{pjc:orbits}
P. J. Cameron, Orbits of permutation groups on unordered sets, I,
\textit{J. London Math. Soc.} (2) \textbf{17} (1978), 410--414; II, ibid.
(2) \textbf{23} (1981), 249--265; III, ibid. (2) \textbf{27} (1983),
229--237; IV, ibid. (2) \textbf{27} (1983), 238--247.
\bibitem{pjc:survey}
P. J. Cameron, Automorphism groups of graphs, in
\textit{Selected Topics in Graph Theory II} (ed. L. W. Beineke and
R. J. Wilson), Academic Press, London, 1983, pp.~89--127.
\bibitem{pjc:oligo}
P. J. Cameron,
\textit{Oligomorphic Permutation Groups},
London Math. Soc. Lecture Notes \textbf{152},
Cambridge University Press Cambridge, 1990.
\bibitem{pjc:list}
P. J. Cameron,
Sequences realised by oligomorphic permutation groups,
\textit{J. Integer Sequences} \textbf{3} (2000), article 00.1.5, available
from
\texttt{}.
\bibitem{ce}
H. Cartan and S. Eilenberg, \textit{Homological Algebra}, Princeton
University Press, Princeton, 1956.
\bibitem{cherlin}
G. L. Cherlin, Homogeneous tournaments revisited,
\textit{Geometriae Dedicata} \textbf{26} (1988), 231--239.
\bibitem{coxeter}
H. S. M. Coxeter, \textit{Regular Complex Polytopes}, Cambridge University
Press, Cambridge, 1974.
\bibitem{dixon}
J. Dixon, The Fitting subgroup of a linear solvable group,
\textit{J. Austral. Math. Soc.} \textbf{7} (1967), 417--424.
\bibitem{er}
P. Erd\H{o}s and A. R\'enyi, Asymmetric graphs,
\textit{Acta Math. Acad. Sci. Hungar.} \textbf{14} (1963), 295--315.
\bibitem{es}
P. Erd\H{o}s and J. Spencer, \textit{Probabilistic Methods in
Combinatorics}, Akad\'emiai Kiad\'o, Budapest, and Academic Press,
New York, 1974.
\bibitem{fraisse}
R. Fra\"{\i}ss\'e,
Sur certains relations qui g\'en\'eralisent
l'ordre des nombres rationnels,
\textit{C. R. Acad. Sci. Paris} \textbf{237} (1953), 540--542.
\bibitem{gw}
D. Gorenstein and J. H. Walter, The characterization of finite
groups with dihedral Sylow $2$-subgroups, I, \textit{J. Algebra}
\textbf{2} (1964), 85--151; II, ibid. \textbf{2} (1964), 218--270;
III, ibid. \textbf{2} (1964), 354--393.
\bibitem{hall}
M. Hall, Jr., \textit{The Theory of Groups},
Macmillan, New York, 1959.
\bibitem{knuth}
D. E. Knuth, \textit{Axioms and Hulls},
Lecture Notes in Computer Science \textbf{606},
Springer, Berlin, 1992.
\bibitem{lachlan}
A. H. Lachlan, Countable homogeneous tournaments,
\textit{Trans. Amer. Math. Soc.} \textbf{284} (1984), 431--461.
\bibitem{lovasz}
L. Lov\'asz, \textit{Combinatorial Problems and Exercises},
Akad\'emiai Kiad\'o, Budapest, and North-Holland, Amsterdam, 1979.
\bibitem{ms}
C. L. Mallows and N. J. A. Sloane,
Two-graphs, switching classes, and Euler
graphs are equal in number,
\textit{SIAM J. Appl. Math.} \textbf{28} (1975), 876--880.
\bibitem{seidel}
J. J. Seidel, Strongly regular graphs of $L_2$ type and of
triangular type,
\textit{Proc. Kon. Nederl. Akad. Wetensch. Ser. A} \textbf{70}
($=$ \textit{Indag. Math.} \textbf{29}) (1967), 188--196.
\bibitem{eis}
N. J. Sloane,
\textit{The On-Line Enyclopedia of Integer Sequences}, available at
\texttt{}.
\end{thebibliography}
\end{document}