Automorphisms and enumeration of switching classes of tournaments

L. Babai and P. J. Cameron

Department of Computer Science University of Chicago Chicago, IL 60637, U. S, A.

                   laci@cs.uchicago.edu

School of Mathematical Sciences Queen Mary and Westfield College London E1 4NS, U. K.

                  P.J.Cameron@qmw.ac.uk

Submitted: December 14, 1999; Accepted: August 1, 2000

Abstract

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 \ 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 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é).

MR Subject Numbers: primary: 20B25; secondary: 05C25, 05C20, 05C30, 05E99

Dedicated to the memory of Paul Erdős

1 Introduction

The concept of switching of graphs (sometimes referred to as Seidel equivalence) was first defined by Seidel [26]. 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 [25] and Goethals (personal communication), and are reported in [8]. It is also noted in [8] 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 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 \ Y (that is, y ∈ Y and z ∈ X \ 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 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 \ Y, leaving all other arcs unaltered.

Observe that in both contexts, switching with respect to Y and to X \ 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 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 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 5 and 6, asserts that 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 5.2).

The proof involves, in Section 6, 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) ≅ G, having the property that every subgroup of G of odd order is the full automorphism group of a tournament in C (Cor. 6.10).

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 5.1).

The enumeration results are given in Section 3, where we count the tournaments in a switching class whose automorphism group is given, and in Section 7, where we count switching classes. The result in Section 3 generalises Brouwer’s enumeration of local orders [6]. 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 [9] (see Section 8).

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éal in September 1996. Finishing touches were put on the paper in 1999. The main result, Theorem 5.2, has been cited as “Theorem 4.4(b)” in [3, p. 1499].

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ős. For a long while, we just stared at the screen in disbelief. Occasionally, we still do.

2 Equivalent objects: Switching classes, oriented two-graphs and S-digraphs

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 {±1} (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 oriented two-graph. Conversely, any oriented twograph 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 double cover of a set X is a set \overline{X} with a surjective map p : \overline{X} → X with the property that |p^{−1}(x)| = 2 for all x ∈ X. An S-digraph D on \overline{X} is a digraph with the properties

(a) for all x ∈ X, the induced digraph on p^{−1}(x) has no arcs;

(b) for all x, y ∈ X with x ≠ y, the induced digraph on p^{−1}({x, y}) is a directed 4-cycle.

It follows that, if a, b ∈ \overline{X}, then a and b are joined by an arc if and only if p(a) ≠ 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 ∈ 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 ∈ 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 ≤ Aut(C) of automorphisms of the switching class C corresponds a group \overline{G} ≤ Aut(D) of automorphisms of the S-digraph D, with ⟨z⟩ ⊴ \overline{G} and \overline{G}/⟨z⟩ ≅ G. (Thus \overline{G} is an extension of the cyclic group of order 2 by G.)

We claim that 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 ∈ \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)/⟨z⟩ = Aut(C).

We summarize our main conclusions.

Proposition 2.1 The automorphism group of the S-digraph D corresponding to the switching class C contains a unique involution z and Aut(D)/⟨z⟩ = Aut(C). Consequently, any group G ≤ Aut(C) acting on the switching class C is a quotient G = \overline{G}/⟨z⟩ where z is the unique involution in the group \overline{G} ≤ Aut(D).

This extension of Aut(C) and its subgroups is crucial for our characterisation of the automorphism groups of switching classes in Sections 5 and 6.

3 Counting tournaments in a switching class

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 [6].

Lemma 3.1 An automorphism of a switching class C of tournaments fixes some tournament in C if and only if it has odd order.

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 ([21], p. 224), ⟨g⟩ is conjugate (in T ⟨g⟩) to the stabiliser of a tournament; that is, g fixes a tournament. □

Theorem 3.2 Let G be the automorphism group of a switching class C of tournaments. Then the number of tournaments in C, up to isomorphism, is

\frac{1}{|G|} ∑_{{g∈G \atop |g| odd}} 2^{orb(g)−1},

where |g| is the order, and orb(g) the number of cycles, of g.

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. □

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 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 local order (see [9]) is defined to be a tournament containing no 4vertex sub-tournament which consists of a vertex dominating or dominated by a 3-cycle. Local orders also appear in the literature under the names locally transitive tournaments [23] or vortex-free tournaments [22].

Lemma 3.3 The following are equivalent for a switching class C of tournaments:

(a) C contains a linear order;

(b) C contains a local order;

(c) C consists entirely of local orders;

(d) the corresponding oriented two-graph is a circular order.

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 \ {v} is a linear order, say v_{1} < ⋯ < v_{n−1}, with the convention that v_{i} < v_{j} if there is an arc from v_{i} to v_{j}. Since T is a local order, there cannot exist i < j < k such that (v, v_{i}), (v_{j}, v) and (v, v_{k}) are arcs, or the converses of these are arcs. Hence, for some i, we either have arcs (v_{j}, v) for j ≤ i and (v, v_{k}) for k > i, 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}, …, v_{i}}. □

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 ϕ(n/d) elements of order n/d for each d dividing n, such an element having d cycles. Hence we obtain:

Theorem 3.4 The number of local orders on n points, up to isomorphism, is

\frac{1}{n} ∑_{{d|n \atop n/d odd}} 2^{d−1}ϕ(n/d). □

This was first proved by Brouwer [6] by means of a correspondence with certain shift register sequences.

Remark 3.5 The number of non-isomorphic tournaments in a switching class on n vertices is at least (3/2n)(2/\sqrt{3})^{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}| ≤ 3^{(n−2)/2} (Dixon [16]), and |G| ≤ (n/3)3^{n/2}. Since |C| = 2^{n−1}, G has at least (3/2n)(2/\sqrt{3})^{n} orbits in C. (Note that no such exponential bound holds for graphs: the switching class of the null graph contains only ⌊n/2⌋ + 1 non-isomorphic graphs.)

Remark 3.6 Almost all switching classes of tournaments on n points have all 2^{n−1} members pairwise non-isomorphic. This is equivalent to Corollary 6.5 which states that almost all switching classes have trivial automorphism groups.

4 Groups with a unique involution

Our main results, Theorems 5.2 and 5.1, characterize the automorphism groups of switching classes. Proposition 2.1 indicates the connection of these groups with groups containing a unique involution. Therefore the following result is a crucial ingredient in both proofs.

Theorem 4.1 For an abstract finite group G, the following are equivalent:

(a) G has cyclic or dihedral Sylow 2-subgroups; (b) there exists a group \overline{G} containing a unique involution z such that \overline{G}/⟨z⟩

is isomorphic to G.

Moreover, the group \overline{G} is uniquely determined by G.

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.

Proof Suppose that (b) holds. Let \overline{S} be a Sylow 2-subgroup of \overline{G}, so that S = \overline{S}/⟨z⟩ is a Sylow 2-subgroup of G. Now \overline{S} contains a unique involution, so it is cyclic or generalised quaternion (Burnside [7], 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 [13]. Extensions of ℤ_{2} by a group G are described by elements of the cohomology group H^{2}(G, ℤ_{2}). If S is a cyclic or dihedral 2-group, then there is an extension \overline{S} of ℤ_{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, ℤ_{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 ∈ G, there is a corresponding class t^{g} of the conjugate S^{g}. We call t stable if the images of t and t^{g} under the restriction maps res_{S,S∩S^{g}} and res_{S^{g},S∩S^{g}} are equal for all g ∈ 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 ([13], 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 ∈ H^{2}(S, ℤ_{2}). So the element t^{∗} = cor_{S,G} t of H^{2}(G, ℤ_{2}) satisfies res_{G,S} t^{∗} = t. The extension \overline{G} of ℤ_{2} by G corresponding to t^{∗} has a unique element of order 2, since each of its Sylow 2-subgroups does. □

Remark 4.2 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) · O(G) (semidirect product, so G/O(G) = S_{2}(G)) by Burnside’s transfer theorem ([7], p. 155). The case when S_{2}(G) is dihedral is settled by the theorem of Gorenstein and Walter [20]:

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 PΓL(2, q) which contains PSL(2, q) (for q odd).

It is possible to prove that (a) implies (b) in Theorem 4.1 using this structural information in place of the cohomological argument, though the proof is much longer.

Remark 4.3 An interesting class of groups with a unique involution, called “binary polyhedral groups,” is discussed by Coxeter ([15], 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 ℂ to the 3-dimensional orthogonal group over ℝ. 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 4.1 settles this question. In particular, groups \overline{G} for which O(G) is not a direct factor in G = \overline{G}/⟨z⟩ 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 = P SL(2, 3) then \overline{G} = SL(2, 3), as expected, but if G = P GL(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)/⟨z⟩ = P GL(2, 3). (The trouble is, GL(2, 3) has non-central involutions as well, its Sylow 2subgroup is dihedral.)

5 Automorphism groups of switching classes

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 admits the permutation group G ≤ Sym(X) if G ≤ Aut(C).

Theorem 5.1 For a finite group G of permutations of a finite set X, the following are equivalent:

(a) there is a switching class of tournaments on X admitting G;

(b) G has cyclic or dihedral Sylow 2-subgroups which act semiregularly on X.

Theorem 5.2 For an abstract finite group G, the following are equivalent:

(a) G is the full automorphism group of a switching class of tournaments;

(b) G has cyclic or dihedral Sylow 2-subgroups.

We first prove that, in each of Theorems 5.1 and 5.2, 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 2.1 and Theorem 4.1 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 ℤ_{2} by G acting on D and inducing G on X, as in Proposition 2.1.

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}/⟨z⟩ acts semiregularly on X.

The reverse implications in Theorems 5.1 and 5.2 use similar constructions. We consider Theorem 5.1 first. Suppose that condition (b) holds. By Theorem 4.1, there is a group \overline{G} with unique involution z, such that \overline{G}/⟨z⟩ = 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 ∈ Y, G_{y} has odd order, and so \overline{G_{y}} has twice odd order. It follows that \overline{G_{y}} = ⟨z⟩ × H, with H ≅ 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 ∉ H, the element z interchanges the two points of \overline{X} covering each point of X.

Furthermore, if t ∈ \overline{G} has 2-power order and interchanges a pair of points a, b ∈ \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) ≠ 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 2, it follows that G acts on a switching class of tournaments. This proves Theorem 5.1. □

In the next section, we complete the proof of Theorem 5.2 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}.

6 Automorphism groups of random G-invariant digraphs

We shall regard a digraph as a function f from ordered pairs of distinct vertices to {±1} 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 random digraph. We allow f to have an arbitrary, (n^{2} − n)-dimensional ±1 distribution. In particular, the projections f(x, y) and f(x′, y′) do not have to be independent even if {x, y} ∩ {x′, y′} = ∅.

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}, …, X_{m}. A set of pairs {(x_{1}, y_{1}), …, (x_{s}, y_{s})} will be called (X_{1}, …, X_{m})-independent, if

(a) no {x_{i}, y_{i}} is a subset of any X_{k};

(b) no {x_{i}, y_{i}, x_{j}, y_{j}} is a subset of any X_{k} ∪ X_{l} for any i ≠ j, 1 ≤ i, j ≤ s, 1 ≤ k, l ≤ m.

Clearly, s ≤ \binom{m}{2} in this case. We shall say that the random digraph f is uniformly distributed between (X_{1}, …, X_{m}) if (A) Prob(f(x, y) = 1) = \frac{1}{2} whenever x and y belong to different classes;

(B) for any (X_{1}, …, X_{m})-independent set {(x_{1}, y_{1}), …, (x_{s}, y_{s})}, the random variables f(x_{i}, y_{i}) (for i = 1, …, s) are totally independent.

Lemma 6.1 Let the n-element set X be partitioned as X = X_{1} ∪ … ∪ X_{m} into pairwise disjoint classes of bounded size: |X_{i}| ≤ t for some fixed t. Let f be a random digraph, uniformly distributed between (X_{1}, …, X_{m}). Then the probability of the event that all but at most m^{1/2+ϵ} of the X_{i} are invariant under Aut(f) is greater than 1−ϵ for any positive ϵ provided that n > n_{0}(t, ϵ).

Proof We say that a permutation α ∈ Sym(X) destroys a set A ⊆ X if A is not invariant under α. Let r(α) denote the number of classes destroyed by α.

For some α ∈ Sym(X), let x_{1}, …, x_{k} be a maximal subset of X such that all the 2k elements x_{1}, …, x_{k}, αx_{1}, …, αx_{k} belong to different classes.

We claim that k ≥ r/(2t + 1), where r = r(α). Indeed, let X_{1}, …, X_{r} be the classes destroyed by α. For each i ≤ r, pick a point z_{i} ∈ X_{i} such that αz_{i} ∉ X_{i}. Now define a graph on the vertex set {1, …, r} by joining i and j if the pair {z_{i}, αz_{i}} is in conflict with the pair {z_{j}, αz_{j}} (conflict meaning that some class X_{ℓ} meets both pairs). Since by assumption all X_{i} have size ≤ t, the vertices of the graph constructed have degree ≤ 2t. Therefore the chromatic number of the graph is at most 2t+1, hence it has an independent set of size ≥ r/(2t + 1), establishing the Claim.

Now the set of k(k − 1) pairs {(x_{i}, x_{j}), (αx_{i}, αx_{j}) : 1 ≤ i < j ≤ k} is (X_{1}, …, X_{m})-independent and therefore the random variables f(x_{i}, x_{j}) and f(αx_{i}, αx_{j}) are totally independent. Hence

Prob(α ∈ Aut(f)) ≤ Prob(f(x_{i}, x_{j}) = f(αx_{i}, αx_{j}) for 1 ≤ i < j ≤ k)
= 2^{−k(k−1)/2}.

Consequently, the probability that there exists as automorphism of f which destroys at least r classes is less than n!2^{−k(k−1)/2}, where k = r/(2t+1). Let us set r = m^{1/2+ϵ}/2. Then clearly n!2^{−k(k−1)/2} < ϵ for n > n_{0}(t, ϵ). 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).

Proposition 6.2 Let G be a finite group acting on a set X. Let A_{1}, …, A_{s} be subsets of X which are not invariant under G. Then there exists α ∈ G which destroys at least half the classes A_{i}.

Proof We use the simple trick sometimes known as the “first moment method” (see [18], p. 5). Let α be a random member of G (each element of G having the same chance to be α). For each i, the probability that A_{i} is invariant under α 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 α is at least s/2. □

Now, an application of Proposition 6.2 with those X_{i} not invariant under G = Aut(f) playing the roles of A_{1}, …, A_{s} completes the proof of Lemma 6.1. □

Next, we turn our attention to random digraphs invariant under a permutation group action.

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-invariant if Prob(G ≤ Aut(f)) = 1; in other words, Prob(f(x, y) = f(gx, gy)) = 1 for all g ∈ G, x, y ∈ X.

We shall need the following stronger version of condition (B):

(B′) If (i_{1}, j_{1}), …, (i_{s}, j_{s}) are distinct pairs of numbers from {1, …, m} such that (i_{h}, j_{h}) ≠ (j_{k}, i_{k}) (k, h = 1, …, s), then the projections f|X_{i_{h}} ×X_{j_{h}} (h = 1, …, s) are totally independent.

We shall say that f is strongly uniformly distributed between (X_{1}, …, X_{m}) if (A) and (B′) hold.

Theorem 6.3 Let G be a group of order t acting semiregularly on the set X, with orbits X_{1}, …, X_{m}. Let f be a random G-invariant digraph on X, strongly uniformly distributed between (X_{1}, …, X_{m}) and satisfying the additional condition (C) below. Then Prob(Aut(f) = G) > 1 − ϵ for any positive ϵ provided that |X| = n > n_{0}(t, ϵ).

(C) For any i ≠ j and any x, x′ ∈ X_{i} and y, y′ ∈ X_{j},

Prob(f(x, y) = f(x′, y′)) ≤ 1/2.

Proof By Lemma 6.1, with probability greater than 1 − ϵ, most orbits of G are invariant under Aut(f)

Let us first consider permutations α ∈ Sym(X) under which all the X_{i} are invariant.

We select representatives x_{i} ∈ X_{i} for i = 1, …, m. Let E_{k} denote the event that there exists α ∈ Aut(X) \ G which preserves the classes X_{i} and fixes precisely k of x_{1}, …, x_{m}. The probability that, for some i > k, the vertex x_{i} “has a place to go” while x_{1}, …, x_{k} are fixed is at most (t − 1)2^{−k}, since the “place” must be some y ∈ X_{i} with y ≠ x_{i}, and

Prob(f(x_{i}, x_{j}) = f(y, x_{j}) for all j = 1, …, k) ≤ 2^{−k}.

(We used (C) (employing semiregularity) and (B′) here.) Using (B′) again, we find that the probability that x_{k+1}, …, x_{m} all have places to go while x_{1}, …, x_{k} are fixed is not greater than ((t − 1)2^{−k})^{m−k}. Finally,

Prob(E_{k}) ≤ \binom{m}{k}((t − 1)2^{−k})^{m−k}.  (1)

Our next observation is that any α ∈ Sym(X) which preserves the X_{i} agrees with some g ∈ G in at least m/t of the x_{i}. (Again, we use the “first moment method”: pick a random g ∈ G; then the expected number of those x_{i} such that αx_{i} = gx_{i} is exactly m/t.) Now g^{−1}α fixes k ≥ m/t of the x_{i}. Hence the probability of the event A that there exists an α ∈ Aut(f) \ G which preserves the X_{i} is

Prob(A) ≤ ∑_{k=k_{0}}^{m} Prob(E_{k}),  (2)

where k_{0} = ⌈m/t⌉.

As above, the probability that any particular member of X_{1} has a place to go while x_{1}, …, x_{m} are fixed is less than (t − 1)2^{−m+1}. Consequently,

Prob(E_{m}) ≤ n(t − 1)2^{−m+1}.  (3)

Combining (1), (2) and (3), we obtain for large enough n (meaning n > 2t^{2} log_{2} t, and therefore t < 2^{m/2t}):

Prob(A) ≤ ∑_{k=k_{0}}^{m} Prob(E_{k})

≤ n(t − 1)2^{−m+1} + ∑_{k=k_{0}}^{m−1} \binom{m}{k}((t − 1)2^{−k})^{m−k}

< 2nt2^{−m} + ∑_{k=1}^{m−1} \binom{m}{k}2^{−k(m−k)/2}

< 2nt2^{−m} + 2 ∑_{k=1}^{m} \binom{m}{k}2^{−km/4}
= 2nt2^{−m} + 2((1 + 2^{−m/4})^{m} − 1)
< 3m2^{−m/4};

hence

Prob(A) < 3m2^{−m/4}.  (4)

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 6.1: it is less than m^{2/3}, say, with probability greater than 1 − ϵ, provided that n > n_{0}(t, ϵ).

Set q = ⌊m^{2/3}⌋. Let us consider those α ∈ Sym(X) which preserve the sets X_{1}, …, X_{m−q}.

Restricting the above result to the subgraph induced by the set Y = X_{1} ∪ … ∪ X_{m−q}, we find that the probability of the existence of such an α ∈ Aut(f) whose restriction to Y is not a member of the restriction of G to Y, is less than

3(m − q)2^{−(m−q)/4} < 2^{−m/5}  (5)

(for large m).

Suppose now that α|Y = g|Y for some g ∈ G. Now g^{−1}α|Y is the identity. We estimate the probability that some x ∈ X \ Y can still move. Let y ∈ X\Y, x ≠ y, and let x_{1}, …, x_{m−q} be representatives of X_{1}, …, X_{m−q}, respectively. We claim that

Prob(f(x, x_{j}) = f(y, x_{j}) for j = 1, …, m − q) ≤ 2^{−m+q}.  (6)

If y belongs to the G-orbit of X then (6) follows from (C) (by semiregularity) and (B′). If y does not belong to Gx then (6) simply follows from (A) and (B) (and we have equality in this case).

Consequently, the probability that there exists α ∈ Aut(f)\G preserving X_{1}, …, X_{m−q} is less than

2^{−m/5} + \binom{qt}{2}2^{−m+q} < 2^{−m/6}.  (7)

Finally,

Prob(Aut(f) ≠ G) = Prob(Aut(f) ≰ G)
≤ Prob(Aut(f) destroys more than q orbits of G)

+\binom{m}{q}2^{−m/6}

< ϵ + m^{q}2^{−m/6}
< 2ϵ

for n > n′_{0}(t, ϵ). □

Remark 6.4 Theorem 6.3 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.

We are now ready to derive the reverse implication in Theorem 5.2 from Theorems 4.1 and 6.3.

Let G be a finite group with cyclic or dihedral Sylow 2-subgroups. By Theorem 4.1, there exists a group \overline{G} containing a single involution z such that G ≅ \overline{G}/⟨z⟩. Let t = |\overline{G}|. Let \overline{G} act semiregularly with orbits X_{1}, …, 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} → X by contracting every orbit of ⟨z⟩. It is this map p with respect to which we shall use the term “S-digraph” (cf. Section 2).

We are going to define random \overline{G}-invariant S-digraphs on \overline{X} with respect to p. Being special, no arcs join any pair x, zx for x ∈ \overline{X}, and for all distinct x, y ∈ \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 6.3, 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 2). □

Applying this argument to the trivial group (|G| = 1) we obtain the following corollary. An object is asymmetric if its automorphism group is trivial.

Corollary 6.5 Almost all switching classes of tournaments are asymmetric. The same holds for switching classes of graphs. □

Corollary 6.5 strengthens the well-known results that almost all labelled graphs (tournaments) are asymmetric ([17]).

Remark 6.6 Similarly, one can derive from Theorem 6.3 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.

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. [24], 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 [2] and [5].)

The above proof of Theorem 5.2 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.

Problem 6.7 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.)

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. [4]).

Remark 6.8 By Remark 6.4 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).

The following observation leads to a further important corollary.

Proposition 6.9 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}/⟨z⟩ 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}.)

Proof Let \overline{H} be the preimage of H in G, so z ∈ \overline{H} and \overline{H}/⟨z⟩ = H. Let K be the (unique) index-2 subgroup of \overline{H}; so \overline{H} = K × ⟨z⟩, and K ≅ H.

Within each \overline{G}-orbit, select a “root.” Making g ∈ \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. □

Hence we have the following corollary:

Corollary 6.10 Given a finite group G with cyclic or dihedral Sylow 2subgroups, 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. □

This answers a question of the second author [10, p. 118].

7 Counting switching classes

The following specialisation of Theorem 5.1 is crucial to the enumeration of switching classes of tournaments. Call a permutation 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}.

Lemma 7.1 A permutation leaves invariant some switching class of tournaments if and only if it is level.

Proof This is immediate from Theorem 5.1 applied to the cyclic group generated by the permutation. □

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 [25]: it is

2^{orb_{2}(g)−orb(g)+δ(g)},

where orb_{2}(g) is the number of orbits of ⟨g⟩ on unordered pairs, and δ(g) is 0 if all cycles of g have even length, or 1 otherwise. (So, if g is level, then δ(g) = 1 or 0 according as |g| is odd or even.) Thus we obtain:

Theorem 7.2 The number of switching classes of tournaments on n vertices, up to isomorphism, is

\frac{1}{n!} ∑_{g∈L_{n}} 2^{orb_{2}(g)−orb(g)+δ(g)}. □

For small values of n, we obtain the following.

n  2 3 4 5 6 7 8
switching classes 1 1 2 2 6 12 79

Remark 7.3 The number of switching classes of tournaments is smaller than the number of switching classes of graphs if n ≥ 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 ≥ 3, then not every permutation is level.

Remark 7.4 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 [25]. 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.

Lemma 7.5 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 \ H is

\frac{1}{|G \ H|} ∑_{g∈G\H} π(g),

where π(g) is the number of fixed points of g in X.

Proof The standard proof of the Orbit-Counting Lemma shows that

∑_{g∈G} π(g) = ∑_{x∈X} |G_{x}|,

and that the right-hand expression is |G| times the number of orbits. Let Y be the set {y : (G \ H) ∩ G_{y} ≠ ∅}. Clearly ∑_{g∈G\H} π(g) is equal to ∑_{y∈Y} |(G\H)∩G_{y}|, which in turn is ((p−1)/p) ∑_{y∈Y} |G_{y}|, where p = |G : H|, since |G_{y} : G_{y} ∩ H| = p. Thus the sum is

\frac{p − 1}{p}|G|# orb(G, Y) = |G \ H|# orb(G, Y). □

Proposition 7.6 The number of switching classes of tournaments on n vertices admitting odd permutations is

\frac{2}{n!} ∑_{g∈L_{n}∩(S_{n}\A_{n})} 2^{orb_{2}(g)−orb(g)}.

Proof Observe that if g ∉ A_{n} then g has even order, so δ(g) = 0 for all g ∈ L_{n} ∩ (S_{n} \ A_{n}). Apply Lemma 7.5. □

Corollary 7.7 If n ≡ 2 (mod 4), then the number of switching classes of tournaments on n vertices whose automorphism groups have even order is

\frac{2}{n!} ∑_{{g∈Ln \atop |g| even}} 2^{orb_{2}(g)−orb(g)}.

Proof If n ≡ 2 (mod 4), a level permutation is odd if and only if its order is even. □

Remark 7.8 This formula is trivially valid also for n odd, and holds as well if n = 4.

Corollary 7.9 If n is a power of 2, there are 2^{n/2}/n cyclic switching classes of tournaments on n vertices.

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. □

There is an alternative direct proof. An n-cycle g fixes 2^{n/2−1} switching classes. If C is one of these, then ⟨g⟩ 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 \frac{1}{2}-transitively on a set of 2-power size. So G = ⟨g⟩. Thus, if two g-invariant switching classes are isomorphic, then the isomorphism between them normalises ⟨g⟩. Since N(⟨g⟩)/⟨g⟩ has order n/2, the number of isomorphism classes is 2^{n/2−1}/(n/2).

Remark 7.10 The number in Corollary 7.9 is equal to the number of local orders on n/2 points.

8 Application: homogeneous models and infinite permutation groups

We conclude the paper with the descriptions of two infinite permutation groups relevant to a problem discussed in [9]. The discussion here will be brief; more detail on the background can be found in [11].

A class C of structures is said to be hereditary if it is closed under taking induced substructures on subsets. It has the amalgamation property if, whenever f_{i} : A → B_{i} are embeddings of structures in C for i = 1, 2, then there exist embeddings g_{i} : B_{i} → C, for some structure C in C, such that f_{1}g_{1} = f_{2}g_{2}.

It follows from a model-theoretic construction due to Fraïssé [19] 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 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 [9], IV).

Lachlan [23] determined all countable homogeneous tournaments (see also Cherlin [14]). There are just three of them: the transitive tournament ℚ, 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 On-Line Encyclopedia of Integer Sequences [27]. The second author is currently compiling a list of sequences which count group orbits on k-tupes in this way [12].

References

[1] L. Babai, On the minimum order of graphs with given group, Canad. Math. Bull. 17 (1974), 467–470.

[2] L. Babai, On the abstract group of automorphisms, in Combinatorics (ed. H. N. V. Temperley), London Math. Soc. Lecture Notes 52, Cambridge University Press, 1981, pp. 1–40.

[3] L. Babai, Automorphism groups, isomorphism, reconstruction, in Handbook of Combinatorics (ed. R. L. Graham, M. Grötschel and L. Lovász), North-Holland, Amsterdam, 1995, pp. 1447–1540.

[4] L. Babai and C. D. Godsil, On the automorphism groups of almost all Cayley graphs, Europ. J. Combinatorics 3 (1982), 9-15.

[5] L. Babai and A. J. Goodman, On the abstract group of automorphisms, in Coding Theory, Design Theory, Group Theory (ed. D. Jungnickel and S. A. Vanstone), Wiley, New York, 1993, pp. 121–143.

[6] A. Brouwer, The enumeration of locally transitive tournaments, Afd. Zuiv. Wisk. 138, Math. Centrum, Amsterdam, 1980.

[7] W. Burnside, Theory of Groups of Finite Order, 2nd edition, Cambridge University Press, 1911, reprinted Dover Publications, New York, 1955.

[8] P. J. Cameron, Cohomological aspects of two-graphs, Math. Z. 157 (1977), 101–119.

[9] P. J. Cameron, Orbits of permutation groups on unordered sets, I, J. London Math. Soc. (2) 17 (1978), 410–414; II, ibid. (2) 23 (1981), 249– 265; III, ibid. (2) 27 (1983), 229–237; IV, ibid. (2) 27 (1983), 238–247.

[10] P. J. Cameron, Automorphism groups of graphs, in Selected Topics in Graph Theory II (ed. L. W. Beineke and R. J. Wilson), Academic Press, London, 1983, pp. 89–127.

[11] P. J. Cameron, Oligomorphic Permutation Groups, London Math. Soc. Lecture Notes 152, Cambridge University Press Cambridge, 1990.

[12] P. J. Cameron, Sequences realised by oligomorphic permutation groups, J. Integer Sequences 3 (2000), article 00.1.5, available from

<http://www.research.att.com/~njas/sequences/JIS/VOL3/
groups.html>.

[13] H. Cartan and S. Eilenberg, Homological Algebra, Princeton University Press, Princeton, 1956.

[14] G. L. Cherlin, Homogeneous tournaments revisited, Geometriae Dedicata 26 (1988), 231–239.

[15] H. S. M. Coxeter, Regular Complex Polytopes, Cambridge University Press, Cambridge, 1974.

[16] J. Dixon, The Fitting subgroup of a linear solvable group, J. Austral. Math. Soc. 7 (1967), 417–424.

[17] P. Erdős and A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar. 14 (1963), 295–315.

[18] P. Erdős and J. Spencer, Probabilistic Methods in Combinatorics, Akadémiai Kiadó, Budapest, and Academic Press, New York, 1974.

[19] R. Fraïssé, Sur certains relations qui généralisent l’ordre des nombres rationnels, C. R. Acad. Sci. Paris 237 (1953), 540–542.

[20] D. Gorenstein and J. H. Walter, The characterization of finite groups with dihedral Sylow 2-subgroups, I, J. Algebra 2 (1964), 85–151; II, ibid. 2 (1964), 218–270; III, ibid. 2 (1964), 354–393.

[21] M. Hall, Jr., The Theory of Groups, Macmillan, New York, 1959.

[22] D. E. Knuth, Axioms and Hulls, Lecture Notes in Computer Science 606, Springer, Berlin, 1992.

[23] A. H. Lachlan, Countable homogeneous tournaments, Trans. Amer. Math. Soc. 284 (1984), 431–461.

[24] L. Lovász, Combinatorial Problems and Exercises, Akadémiai Kiadó, Budapest, and North-Holland, Amsterdam, 1979.

[25] C. L. Mallows and N. J. A. Sloane, Two-graphs, switching classes, and Euler graphs are equal in number, SIAM J. Appl. Math. 28 (1975), 876–880.

[26] J. J. Seidel, Strongly regular graphs of L_{2} type and of triangular type, Proc. Kon. Nederl. Akad. Wetensch. Ser. A 70 (= Indag. Math. 29) (1967), 188–196.

[27] N. J. Sloane, The On-Line Enyclopedia of Integer Sequences, available

at <http://www.research.att.com:80/~njas/sequences/>.