Séminaire Lotharingien de Combinatoire 71 (2014), Article B71c

NORMALLY REGULAR DIGRAPHS, ASSOCIATION SCHEMES AND RELATED COMBINATORIAL STRUCTURES

L. K. Jørgensen^{a}, G. A. Jones^{b}, M. H. Klin^{c,1}, and S. Y. Song^{d}

aDept. of Math. Sciences, Aalborg University, Fr. Bajers Vej 7, 9220 Aalborg, Denmark

bDept. of Mathematics, University of Southampton, Southampton, SO17 1BJ, UK

cDept. of Mathematics, Ben-Gurion University, P.O.Box 653, Beer Sheva 84105, Israel

dDept. of Mathematics, Iowa State University, Ames, Iowa, 50011, USA

Abstract. This paper reports on the characteristics of and mutual relationships between various combinatorial structures that give rise to certain imprimitive non-symmetric three-class association schemes. The relation graphs of an imprimitive symmetric 2-class association scheme are isomorphic to m ∘ K_{r} (the union of m copies of the complete graph on r vertices) and its complement \overline{m ∘ K_{r}} (the complete m-partite strongly regular graph) for some positive integers m and r. The set of relation graphs of a non-symmetric three-class fission scheme of such a 2-class association scheme contains a pair of opposite orientations of either m ∘ K_{r} or \overline{m ∘ K_{r}}, depending on m and r. For suitable parameters m and r, these graphs arise from various combinatorial objects, such as doubly regular tournaments, normally regular digraphs, skew Hadamard matrices, Cayley graphs of dicyclic groups and certain group rings. The construction and the characteristics of these objects are investigated combinatorially and algebraically, and their mutual relationships are discussed.

Key words and phrases. Cayley graphs, regular team tournaments, skew symmetric Hadamard matrices, S-rings, normally regular digraphs, association schemes.

1Partially supported by Department of Mathematical Sciences, University of Delaware, Newark, DE 19716.

2 L. K. JØRGENSEN, G. A. JONES, M. H. KLIN, AND S. Y. SONG

Contents

1. Introduction 2 2. Preliminaries 4 3. Main combinatorial structures 6 3.1. Doubly regular tournaments 6 3.2. Doubly regular orientations of \overline{m ∘ K_{r}} 10 3.3. Normally regular digraphs 11 3.4. Association schemes and their relation graphs 15 4. Characterisation of doubly regular (m, r)-team tournaments 17 4.1. Three types of graphs 17 4.2. Doubly regular (m, 2)-team tournaments 20 5. Equivalence of main structures 21 5.1. Simple corollaries 21 5.2. Type II doubly regular (m, r)-team tournaments with r > 2 23 6. Vertex transitive doubly regular team tournaments 24 7. Cayley graphs and group rings 27 8. Ito’s Conjecture and S-rings over dicyclic groups 30 9. Concluding remarks 34 10. Acknowledgements 37 References 37

1. Introduction

A non-symmetric three-class association scheme consists of three nontrivial associate relations, two of which are non-symmetric relations. If A is the adjacency matrix of one of the two non-symmetric relations, then A^{t} is the adjacency matrix of the directed graph associated with the other (opposite) non-symmetric relation. The undirected graph associated with the symmetric relation has adjacency matrix J −I −A−A^{t} (see Section 2 for all definitions). As they are the relation graphs of an association scheme, it is required that these graphs are regular, in particular that AJ = JA = kJ for some number k, and that

(1) AA^{t} = A^{t}A is a linear combination of I, A, A^{t} and J − I − A − A^{t}, and

(2) A^{2} is a linear combination of I, A, A^{t} and J − I − A − A^{t}. There are many combinatorial structures that possess either of these characteristics. This paper concerns the construction of such structures and studies their relationships. Among others, it discusses

• normally regular digraphs, i.e., regular directed graphs satisfying condition 1, and • doubly regular team tournaments, i.e., regular orientations of a complete multi-

partite graph satisfying condition 2.

The paper also surveys the basic properties of other related objects, including Cayley graphs and skew Hadamard matrices. It gives valuable descriptions of their mutual relationships and interpretations of certain characteristics of an object in terms of other structures. The organisation of the paper is as follows.

In Section 2, we briefly recall basic terminology and notation for graphs including matrix representations and automorphisms of graphs.

In Section 3, we describe our main objects, doubly regular tournaments, doubly regular orientations of complete multipartite strongly regular graphs, normally regular digraphs and association schemes. To keep the presentation reasonably self-contained we recall known examples and their constructions, and we compare the characteristics of these objects. In particular, the doubly regular tournaments obtained from other doubly regular tournaments T via the coclique extension (denoted by C_{r}(T)) and a special way of ‘doubling’ and ‘augmenting’ with an additional pair of vertices (denoted by D(T)), are equivalent to normally regular digraphs with certain parameter conditions. These objects are also related to a certain class of doubly regular team tournaments and imprimitive symmetrisable 3-class association schemes.

In Section 4, we focus on the characterisation of doubly regular (m, r)-team tournaments which may be viewed as the orientations of complete multipartite strongly regular graphs \overline{m ∘ K_{r}}. We then treat the (m, 2)-team tournaments as a special class in connection with symmetrisable 3-class association schemes.

In Section 5, the relationships between the first relation graphs of imprimitive nonsymmetric 3-class association schemes and special types of doubly regular tournaments C_{r}(T) and D(T) are discussed. In particular, it is shown that every imprimitive nonsymmetric 3-class association scheme for which the first relation graph is an orientation of \overline{m ∘ K_{r}} for r = 2 is characterized by the relation graph being isomorphic to either C_{2}(T) or D(T) for a suitable doubly regular tournament T. In Section 5.2 we give a short survey of first relation graphs of imprimitive non-symmetric 3-class association schemes with r ≥ 3, other than C_{r}(T).

In Section 6, we study the groups acting transitively on a graph D(T) for some doubly regular tournament T. In particular, we study the automorphism group of a vertex transitive doubly regular tournament D(T). We observe that for any tournament T the graph D(T) has a unique involutory automorphism. We also show that the Sylow 2-subgroups of the automorphism group of D(T) are not cyclic but are generalised quaternion groups.

In Section 7, many normally regular digraphs arise from Cayley graphs, group rings and difference sets. We investigate the conditions on the connection set S ⊂ G under which the Cayley graph Cay(G, S) is a normally regular digraph. We then reformulate the condition in terms of group rings. We also show that if the Cayley graph of G with the generating set D \ {1} is isomorphic to D(T) for some doubly regular tournament T, then D gives rise to a certain relative difference set.

In Section 8, we recall Noburo Ito’s conjecture [Ito97] concerning Hadamard groups and matrices, and consider S-rings over dicyclic groups to provide a reinterpretation of the conjecture. Ito’s conjecture states that every dicyclic group of order 8t, for some t, is a Hadamard group. We consider possible values of t for which the dicyclic group of order 8t is a skew Hadamard group. Earlier in [Ito94], Ito proved that the Hadamard matrices corresponding to Paley tournaments P_{q} can be constructed from skew Hadamard groups. We state and prove the result in terms of D(P_{q}): that is, we show that SL(2, q) acts as a group of automorphisms of D(P_{q}) and that this group contains a dicyclic subgroup acting regularly on the vertex set. We then give examples, found by computer search using GAP and GRAPE, showing that other groups besides the dicyclic groups may appear as regular subgroups of the automorphism groups of the graphs D(P_{q}) for some q.

In Section 9, we give some concluding remarks. In particular, we emphasise the quite unusual 20-year history of this project, discussing the reasons for its style and goals of presentation, and briefly mentioning ongoing progress in all areas considered since the project began.

2. Preliminaries

A directed graph Γ consists of a finite set V (Γ) of vertices and a set E(Γ) ⊆ {(x, y) | x, y ∈ V (Γ)} of arcs (or directed edges). If (x, y) ∈ E(Γ), then we say that x and y are adjacent, x dominates y, and that y is an out-neighbour of x. (We also denote this by x → y.) The set of out-neighbours of x is the set N^{+}(x) = {y ∈ V (Γ) | (x, y) ∈ E(Γ)}. The out-valency of x is the number |N^{+}(x)| of out-neighbours of x. In-neighbours and in-valency are defined similarly. We say that Γ is regular of valency k if every vertex in Γ has in-valency and out-valency k.

A (simple) graph can be viewed as a directed graph Γ for which (x, y) ∈ E(Γ) if and only if (y, x) ∈ E(Γ). An oriented graph is a directed graph Γ where at most one of the arcs (x, y) and (y, x) is in E(Γ). In the next sections, by a directed graph we usually refer to an oriented graph.

The adjacency matrix of a directed graph Γ with V (Γ) = {x_{1}, …, x_{n}} is an n × n matrix A where its (i, j)-entry (A)_{ij} = a_{ij} is defined by

a_{ij} = \begin{cases}1, & if (x_{i}, x_{j}) ∈ E(Γ), \\ 0, & otherwise. \end{cases}

The matrix J = J_{n} is the n × n matrix with 1 in every entry, and I = I_{n} denotes the n × n identity matrix. Thus J − I is the adjacency matrix of the complete graph on n vertices.

In addition to the ordinary matrix multiplication we will use two other matrix products. Let A and B be n × n matrices. Then the Schur-Hadamard product A ∘ B is the n × n matrix obtained by the entry-wise multiplication: (A ∘ B)_{ij} = a_{ij}b_{ij}. For an n × n matrix A and an m×m matrix B we define the Kronecker product of A and B to be the nm×nm block matrix

A ⊗ B = [ \begin{matrix}a_{11}B & … & a_{1n}B \\ ⋮ & & ⋮ \\ a_{n1}B & … & a_{nn}B \end{matrix} ] .

[figure: u; w; v; w_{2}; w_{1}; v_{2}; v_{1}; u_{1}; u_{2}]

Figure 1. Cycle of length 3 and its 2-coclique extension.

The following lemma is an immediate consequence of the definition.

Lemma 2.1. Let A and B be n × n matrices and let C and D be m × m matrices. Then

(A ⊗ C)(B ⊗ D) = (AB) ⊗ (CD).

A coclique extension of a given directed graph Γ may be conveniently defined by a Kronecker product of matrices as follows.

Definition 2.2. Let Γ be a directed graph with adjacency matrix A. The directed graph with adjacency matrix A ⊗ J_{s} is called a coclique extension of Γ, and denoted by C_{s}(Γ).

Thus C_{s}(Γ) is the graph obtained from Γ by replacing each vertex v with s new vertices, say v_{1}, …, v_{s}. The vertices v_{1}, …, v_{s} form a coclique, i.e., they are pairwise non-adjacent. If w is replaced with w_{1}, …, w_{s} then v_{i} → w_{j} is an edge if and only if v → w.

Example 2.3. Let us start with the matrix A = [ \begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix} ]. Then clearly we have

A ⊗ J_{2} = [ \begin{matrix}0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \end{matrix} ] .

In Figure 1 we depict two graphs, for which the matrices A and A ⊗ J_{2} serve as adjacency matrices, respectively.

Given a permutation g of a set X, we use the notation x^{g} for the image of x ∈ X under g. An automorphism of a directed graph Γ is a permutation of V (Γ) such that (x, y) ∈ E(Γ) if and only if (x^{g}, y^{g}) ∈ E(Γ). The set Aut(Γ) of all automorphisms of Γ forms a group called the automorphism group of Γ. Any subgroup of this group is called a group of automorphisms. A group G of automorphisms is said to be semiregular if for any two vertices x and y, there is at most one g ∈ G such that x^{g} = y, and G is said to be transitive if for any two vertices x and y, there is at least one g ∈ G such that x^{g} = y. If G is both semiregular and transitive then we say that G is regular.

Given a group G and a set S ⊂ G, we define the Cayley graph of G with connection set S to be the (directed) graph Cay(G, S) with vertex set G and arc set {(x, y) | x^{−1}y ∈ S}. We always assume that 1 ∉ S, where 1 denotes the identity of the group, so that the Cayley graph has no loops. If S = S^{(−1)}, where S^{(−1)} denotes the set {s^{−1} | s ∈ S}, then Cay(G, S) is an undirected graph. If S ∩ S^{(−1)} = ∅ then Cay(G, S) is an oriented graph. It is known that a graph Γ is a Cayley graph of a group G if and only if G is a regular group of automorphisms of Γ.

We will, in particular, consider Cayley graphs of dicyclic groups. The dicyclic group of order 4n is the group

⟨x, y | x^{n} = y^{2}, y^{4} = 1, xyx = y⟩.

The dicyclic group of order 8 is the quaternion group. A dicyclic group of order a power of 2 is also called a generalised quaternion group.

3. Main combinatorial structures

In this section, the structure and construction of various classes of doubly regular tournaments, doubly regular (m, r)-team tournaments and normally regular digraphs will be described. These are the combinatorial structures that are relevant to the three-class association schemes we are interested in. Some of the mutual relationships between the above objects will also be described.

3.1. Doubly regular tournaments. A tournament is a directed graph T with the property that for any two distinct vertices x and y, either (x, y) or (y, x), but not both, belongs to E(T). In terms of the adjacency matrix A, a tournament is a directed graph with the property that A + A^{t} + I = J. If every vertex in a tournament T with n vertices has out-valency k then every vertex has in-valency n − k − 1. Therefore, k = n − k − 1, i.e., n = 2k + 1, so such a tournament is a regular directed graph of valency k.

Definition 3.1 ([ReiB72]). A tournament T is called doubly regular if it is regular and for every vertex x in T the out-neighbours of x span a regular tournament.

Example 3.2. Let us consider the Cayley graph Γ = Cay(ℤ_{7}, X) over the cyclic group ℤ_{7}, defined by the connection set X = {1, 2, 4}. The graph Γ is depicted in Figure 2. By inspection, Γ is a tournament in which the out-neighbours of the vertex 0 induce a directed triangle. The same applies to every vertex, so Γ is an example of a doubly regular tournament.

Lemma 3.3. Suppose that T is a tournament with |V (T)| = 4λ+3, and that its adjacency matrix A satisfies

(a) either AJ = (2λ + 1)J or JA = (2λ + 1)J, and

(b) either A^{2} = λA + (λ + 1)A^{t}, AA^{t} = λJ + (λ + 1)I or A^{t}A = λJ + (λ + 1)I.

[figure: 0; 1; 2; 3; 4; 5; 6]

Figure 2. Cayley graph on 7 vertices.

Then all of these equations are satisfied and T is a doubly regular tournament. Conversely, if T is a doubly regular tournament then |V (T)| = 4λ+3 and the adjacency matrix satisfies all of the equations in (a) and (b).

Proof. If we multiply the equation A + A^{t} = J − I by J we get JA + JA^{t} = (n − 1)J = (4λ + 2)J. Thus JA = (2λ + 1)J if and only if JA^{t} = (2λ + 1)J. The transpose of the second equation is AJ = (2λ + 1)J. Using the equations AJ = JA = (2λ + 1)J and A + A^{t} = J − I, it can be shown that the equations involving A^{2}, AA^{t} and A^{t}A are equivalent.

Suppose that T is a doubly regular tournament with n vertices. Then it is regular of valency k = \frac{n−1}{2}. The subgraph spanned by the out-neighbours of a vertex is regular of valency λ = \frac{k−1}{2} = \frac{n−3}{4}. Thus n = 4λ + 3. Every vertex has out-valency 2λ + 1, so JA = (2λ + 1)J. Let x and y be vertices with (x, y) ∈ E(T). Then y has out-valency λ in N^{+}(x); i.e., x and y have exactly λ common out-neighbours. From this (and the fact that every vertex has out-valency 2λ + 1) it follows that AA^{t} = λJ + (λ + 1)I.

Conversely, if AJ = (2λ + 1)J then every vertex has out-valency 2λ + 1. Thus T is regular. If AA^{t} = λJ + (λ + 1)I then for every vertex x the out-neighbours of x span a subtournament in which every vertex has out-valency λ. Thus this subtournament is regular and so T is doubly regular. □

Corollary 3.4. Let x and y be vertices in a doubly regular tournament T with 4λ + 3 vertices and suppose that (x, y) ∈ E(T). Then the number of directed paths of length 2 from x to y is λ, the number of directed paths of length 2 from y to x is λ + 1, the number of common out-neighbours of x and y is λ, and the number of common in-neighbours of x and y is λ.

Below we discuss a couple of classical infinite series.

Paley [Pal33] constructed an infinite family of Hadamard matrices that corresponds to the following family of doubly regular tournaments. These tournaments are called Paley tournaments (cf. Theorems 3.5, 3.7 and 3.12 for the relationship with Hadamard matrices).

Theorem 3.5 ([Pal33]). Let q ≡ 3 mod 4 be a prime power. Let 𝔽_{q} denote the field of q elements and let Q be the set of nonzero squares in 𝔽_{q}. Then the graph P_{q} with V (P_{q}) = 𝔽_{q} and E(P_{q}) = {(x, y) | y − x ∈ Q} is a doubly regular tournament.

Thus the Paley tournament P_{q} is the Cayley graph Cay(𝔽_{q}^{+}, Q) of the additive group 𝔽_{q}^{+}.

Lemma 3.6. The Cayley graph Cay(𝔽_{q}^{+}, −Q) is isomorphic to P_{q}.

Proof. Multiplication by −1 defines an isomorphism between Cay(𝔽_{q}^{+}, Q) and Cay(𝔽_{q}^{+}, −Q). □

Theorem 3.7 (See e.g. [Pas92]). Suppose that A is the adjacency matrix of a doubly regular tournament of order n. Then the matrix

B = [ \begin{matrix}0 & 1 & ⋯ & 1 & 0 & ⋯ & 0 \\ 0 \\ ⋮ & & A & & & A + I \\ 0 \\ 1 \\ ⋮ & & A & & & A^{t} \\ 1 \end{matrix} ]

is the adjacency matrix of a doubly regular tournament of order 2n + 1.

Proof. It is clear that B is the adjacency matrix of a regular tournament of valency n. An easy computation also shows that B satisfies the equation BB^{t} = (k + 1)I_{2n+1} + kJ_{2n+1} where k = (n − 1)/2. □

Another family of doubly regular tournaments was found by Szekeres [Sze69].

Theorem 3.8. Let q ≡ 5 mod 8 be a prime power. Let 𝔽_{q} be the field of q elements and let Q be the unique subgroup of 𝔽_{q}^{∗} of index 4. Let Q, −Q, R, −R be the cosets of Q. Then the graph Sz_{q} with vertex set

{v} ∪ {x_{i} | x ∈ 𝔽_{q}, i = 1, 2}

and arc set

{(v, x_{1}), (x_{1}, x_{2}), (x_{2}, v) | x ∈ 𝔽_{q}} ∪ {(x_{1}, y_{1}) | y − x ∈ Q ∪ R} ∪ {(x_{2}, y_{2}) | y − x ∈ −Q ∪ −R} ∪ {(x_{i}, y_{3−i}) | y − x ∈ Q ∪ −R, i = 1, 2}

is a doubly regular tournament of order 2q + 1.

Two more new constructions of doubly regular tournaments as Cayley graphs were presented by Ding and Yuan [DinY06] and by Ding, Wang and Xiang [DinWX07]. We refer to [Muz10], where Muzychuk constructed exponentially many doubly regular tournaments as Cayley graphs over an elementary abelian group of order q^{3}.

Doubly regular tournaments are also obtained from a class of Hadamard matrices.

Definition 3.9. An n×n matrix H with entries ±1 is called a Hadamard matrix of order n if

HH^{t} = nI.

The condition HH^{t} = nI implies that any two distinct rows of H are orthogonal. Multiplication of any row or any column by −1 preserves this condition. Permutation of the rows and permutation of the columns also preserve the condition.

Definition 3.10. Let H_{1} and H_{2} be Hadamard matrices of order n. Then we say that H_{1} and H_{2} are equivalent if H_{2} can be obtained from H_{1} by permuting rows, permuting columns and multiplying some rows and/or columns by −1.

It is known that if a Hadamard matrix of order n > 2 exists then n ≡ 0 mod 4. The well-known Hadamard matrix conjecture states that there exists a Hadamard matrix of order n for every n divisible by 4. We are interested in the following class of Hadamard matrices.

Definition 3.11. A Hadamard matrix H is called skew if

H + H^{t} = −2I.

This implies that H is skew if H = (h_{ij}) satisfies h_{ij} = −h_{ji} for all i ≠ j, and h_{ii} = −1 for all i.

A new skew Hadamard matrix can be obtained from an old one by simultaneously multiplying the ith row and the ith column by −1 for any i. By repeating this procedure we can transform any skew Hadamard matrix to a skew Hadamard matrix of the following form

(3.1)  H = [ \begin{matrix}−1 & 1 & ⋯ & 1 \\ −1 \\ ⋮ & & B \\ −1 \end{matrix} ]

where B is an (n−1)×(n−1) matrix with entries ±1. Reid and Brown [ReiB72] proved the following equivalence between skew Hadamard matrices and doubly regular tournaments.

Theorem 3.12. Let H and B be matrices satisfying Equation (3.1). Then H is a skew Hadamard matrix of order n if and only if A = \frac{1}{2}(B + J) is the adjacency matrix of a doubly regular tournament with n − 1 vertices.

The proof follows by matrix computations and the properties of the adjacency matrix of a doubly regular tournament in Lemma 3.3.

If A_{1} and A_{2} are adjacency matrices of isomorphic doubly regular tournaments, then A_{2} can be obtained from A_{1} by applying the same permutation to rows and columns. Thus the Hadamard matrices constructed from A_{1} and A_{2} are equivalent. But it is also possible that non-isomorphic doubly regular tournaments correspond to equivalent skew Hadamard matrices.

The investigation of skew Hadamard matrices and their diverse links with other combinatorial structures is definitely a topic of independent interest. Papers such as [IonK03] and [NozS12] provide a small sample of related results.

3.2. Doubly regular orientations of \overline{m ∘ K_{r}}. Let m ∘ K_{r} denote the disjoint union of m copies of the complete graph on r vertices, and let \overline{m ∘ K_{r}} denote its complement, i.e., the complete multipartite graph with m independent sets of size r. Let Γ be an orientation of \overline{m ∘ K_{r}}, i.e., every edge \{a, b\} in \overline{m ∘ K_{r}} is replaced with one of the arcs (a, b) or (b, a). Then we say that Γ is an (m, r)-team tournament.

Remark. The suggested name emphasises that there are m teams of size r, and that each member plays against all the members of the other teams, but against none of his own team. The authors feel that this terminology is consistent with the traditional use of the word “tournament” in graph theory, while future possible alternatives to this suggestion are welcome.

Definition 3.13. An (m, r)-team tournament Γ with adjacency matrix A is said to be doubly regular if there exist integers k, α, β, γ such that

i) Γ is regular with valency k, ii) A^{2} = αA + βA^{t} + γ(J − I − A − A^{t}).

Note that the equation A^{2} = αA + βA^{t} + γ(J − I − A − A^{t}) means that the number of directed paths of length 2 from a vertex x to a vertex y is α if (x, y) ∈ E(Γ), β if (y, x) ∈ E(Γ), and γ if {x, y} is an edge of m ∘ K_{r}.

Proposition 3.14. Let T be a doubly regular tournament of order m = 4λ + 3 and let r ∈ ℕ. Then the coclique extension C_{r}(T) of T is a doubly regular (m, r)-team tournament.

Proof. Let A be the adjacency matrix of T. Then, by Lemma 2.1, the adjacency matrix A ⊗ J_{r} of C_{r}(T) satisfies

(A ⊗ J_{r})^{2} = A^{2} ⊗ J_{r}^{2} = (λA + (λ + 1)A^{t}) ⊗ rJ_{r} = rλ(A ⊗ J_{r}) + r(λ + 1)(A ⊗ J_{r})^{t}.

□

We also have another construction of doubly regular team tournaments from doubly regular tournaments.

Definition 3.15. Let T be a tournament with adjacency matrix A. Then the graph with adjacency matrix

[ \begin{matrix}0 & 1 ⋯ 1 & 0 & 0 ⋯ 0 \\ 0 & & 1 \\ ⋮ & A & ⋮ & A^{t} \\ 0 & & 1 \\ 0 & 0 ⋯ 0 & 0 & 1 ⋯ 1 \\ 1 & & 0 \\ ⋮ & A^{t} & ⋮ & A \\ 1 & & 0 \end{matrix} ]

is denoted by D(T).

In other words, if T = (V, E) is a tournament with V = {x_{1}, …, x_{n}} then D(T) is the graph with vertex set {v_{0}, v_{1}, …, v_{n}, w_{0}, w_{1}, …, w_{n}} and arc set

{(v_{0}, v_{i}), (v_{i}, w_{0}), (w_{0}, w_{i}), (w_{i}, v_{0}) | i = 1, …, n} ∪ {(v_{i}, v_{j}), (v_{j}, w_{i}), (w_{i}, w_{j}), (w_{j}, v_{i}) | (x_{i}, x_{j}) ∈ E}.

Proposition 3.16. For any doubly regular tournament T of order m = 2k + 1 = 4λ + 3, the graph D(T) is a doubly regular (m + 1, 2)-team tournament.

Proof. Let D be the adjacency matrix of D(T). Then an easy computation shows that

(3.2)  D^{2} = kD + kD^{t} + m(J − I − D − D^{t}).

□

3.3. Normally regular digraphs. The notion of a normally regular digraph was suggested by Jørgensen in [Jør94b] as a possible generalisation of the notion of strongly regular graphs. For the reader’s convenience we provide here a short digest of some of the most important facts regarding this notion, in particular some facts about orientations of \overline{m ∘ K_{r}} that are normally regular digraphs.

Definition 3.17. A directed graph Γ with v vertices and adjacency matrix A is called a normally regular digraph with parameters (v, k, λ, μ) if

(i) AA^{t} = kI + λ(A + A^{t}) + μ(J − I − A − A^{t}), and (ii) A + A^{t} is a {0, 1}-matrix.

The condition (i) says that, for any pair x, y of vertices, the number of common outneighbours of x and y is

k, if x = y,
λ, if x and y are adjacent, i.e., if either (x, y) or (y, x) is in Γ,
μ, if x and y are nonadjacent.

In particular, every vertex has out-valency k, i.e., AJ = kJ. The second condition says that, for any pair x, y of vertices, at most one of the arcs (x, y) and (y, x) is present in the directed graph.

Example 3.18. We present two small normally regular digraphs constructed as Cayley graphs over cyclic groups.

(1) The Cayley graph Cay(ℤ_{13}, {1, 3, 9}) is a normally regular digraph with parameters (13, 3, 0, 1).

(2) The Cayley graph Cay(ℤ_{19}, {1, 4, 6, 7, 9, 11}) is a normally regular digraph with parameters (19, 6, 1, 3). This is the smallest graph from the infinite series constructed in Theorem 3.21.

One may consider general normally regular digraphs, satisfying condition (i) but not necessarily (ii). However in this paper it is natural to require condition (ii), as we investigate relations to other structures satisfying (ii).

It is convenient to introduce two new parameters

η = k − μ + (μ − λ)^{2} and ρ = k + μ − λ.

The matrix equation in the definition of normally regular digraphs can be written as follows

(A + (μ − λ)I)(A + (μ − λ)I)^{t} = (k − μ + (μ − λ)^{2})I + μJ.

Thus the matrix B = (A + (μ − λ)I) satisfies the following equations

BB^{t} = ηI + μJ

and (as AJ = kJ)

BJ = ρJ.

Proposition 3.19 ([Jør94b]). If A is the adjacency matrix of a normally regular digraph then A is normal, i.e.,

A^{t}A = AA^{t}.

Proof. It is sufficient to prove that B is normal. Suppose first that B is singular. Then one of the eigenvalues of ηI + μJ is zero: η = 0 or η + μv = 0. Since μ, v ≥ 0 this is possible only when η = k − μ + (μ − λ)^{2} = 0. This implies that k = μ = λ. But if k > 0 then the k out-neighbours of a vertex span a λ-regular graph and so k ≥ 2λ + 1. Thus B is nonsingular.

From BJ = ρJ we get ρ^{−1}J = B^{−1}J and

(3.3)  B^{t} = B^{−1}(BB^{t}) = B^{−1}(ηI + μJ) = ηB^{−1} + μρ^{−1}J.

Using the fact that J is symmetric, we deduce from this that

ρJ = (BJ)^{t} = JB^{t} = ηJB^{−1} + μρ^{−1}J^{2} = ηJB^{−1} + μρ^{−1}vJ.

This implies that

JB^{−1} = \frac{ρ − μρ^{−1}v}{η} J,

and so

vJ = J^{2} = (JB^{−1})(BJ) = \frac{ρ − μρ^{−1}v}{η} ρvJ.

Thus

(3.4)  \frac{ρ − μρ^{−1}v}{η} = ρ^{−1},

and JB^{−1} = ρ^{−1}J or ρJ = JB. Now Equation (3.3) implies that

B^{t}B = ηI + μρ^{−1}JB = ηI + μJ = BB^{t}.

Thus we also have A^{t}A = AA^{t}. □

Corollary 3.20. A normally regular digraph is a regular graph of valency k, i.e.,

AJ = JA = kJ

and the number of common in-neighbours of vertices x and y is equal to the number of common out-neighbours of x and y.

Since the graph is regular we can now count pairs of vertices (y, z) with x → y ← z, z ≠ x, where x is a fixed vertex, in two ways. We get

(3.5)  k(k − 1) = 2kλ + (n − 1 − 2k)μ,

which is equivalent to Equation (3.4).

The preprint [Jør94b] and its update [Jør14] contain many examples of normally regular digraphs, as well as numerical restrictions on their parameters. We present one such result below, referring to the proof of Theorem 31 in [Jør14].

Theorem 3.21 ([Jør94b]). Let k be a multiple of 3, such that k+1 is a prime power. Then there exists a normally regular digraph with parameters (\frac{k^{2}+3k+3}{3}, k, 1, 3), which appears as a Cayley graph over the cyclic group of order \frac{k^{2}+3k+3}{3}.

For any normally regular digraph we have 0 ≤ μ ≤ k. We next give a structural characterisation of normally regular digraphs with equality in one of these inequalities.

Theorem 3.22 ([Jør94b]). A directed graph Γ is a normally regular digraph with μ = k if and only if Γ is isomorphic to C_{s}(T) for some doubly regular tournament T and natural number s.

Proof. It is easy to verify that if T is a doubly regular tournament on 4t + 3 vertices then C_{s}(T) is a normally regular digraph with (v, k, λ, μ) = (s(4t + 3), s(2t + 1), st, s(2t + 1)).

Suppose that Γ is a normally regular digraph with μ = k. Suppose that x and y are non-adjacent vertices in Γ. Then, as μ = k, N^{+}(x) = N^{+}(y). If z is another vertex not adjacent to x then N^{+}(z) = N^{+}(x) = N^{+}(y). Since λ ≤ \frac{k−1}{2}, y and z are nonadjacent. Non-adjacency is thus a transitive relation on the vertex-set, which is therefore partitioned into classes, say V_{1}, …, V_{r}, such that any two vertices are adjacent if and only if they belong to distinct classes.

Suppose that x ∈ V_{i} dominates y ∈ V_{j}, where 1 ≤ i, j ≤ r. Then every vertex x′ ∈ V_{i} dominates every vertex y′ ∈ V_{j}. For if x ≠ x′ then x and x′ are non-adjacent and have the same out-neighbours, so that x′ → y, and similarly x′ → y′. We also have 2k = |N^{+}(x)| + |N^{−}(x)| = v − |V_{i}|. Thus Γ is isomorphic to C_{s}(T) for some regular tournament T and s = v − 2k.

If v → w is an arc in T then it follows that the number of common out-neighbours of v and w in T is \frac{λ}{s}. It follows from Lemma 3.3 that T is a doubly regular tournament. □

Theorem 3.23 ([Jør94b]). A connected graph Γ is a normally regular digraph with μ = 0 if and only if Γ is isomorphic to T or D(T) for some doubly regular tournament T, or Γ is a directed cycle.

Proof. It is easy to verify that if Γ is a doubly regular tournament T or a directed cycle then Γ is a normally regular digraph with μ = 0. (Since a doubly regular tournament has no pairs of non-adjacent vertices, μ is arbitrary but we may choose μ = 0.)

Suppose that Γ is isomorphic to D(T) for some doubly regular tournament T with adjacency matrix A as in Definition 3.15. If the order of T is s = 2ℓ + 1 then, by Lemma 3.3, the adjacency matrix D of D(T) satisfies

(3.6)  DD^{t} = [ \begin{matrix}s & ℓ … ℓ & 0 & ℓ … ℓ \\ ℓ & & ℓ \\ ⋮ & ℓJ + (ℓ + 1)I & ⋮ & ℓ(A + A^{t}) \\ ℓ & & ℓ \\ 0 & ℓ … ℓ & s & ℓ … ℓ \\ ℓ & & ℓ \\ ⋮ & ℓ(A + A^{t}) & ⋮ & ℓJ + (ℓ + 1)I \\ ℓ & & ℓ \end{matrix} ] = sI + ℓ(D + D^{t}).

Thus Γ is a normally regular digraph with parameters (v, k, λ, μ) = (2s + 2, s, ℓ, 0).

Let Γ be a connected normally regular digraph with μ = 0. Suppose that Γ is not a directed cycle. Then k ≥ 2. If Γ is a tournament then it follows from Lemma 3.3 that T is a doubly regular tournament. So we may assume that Γ is not a tournament. Let x be a vertex in Γ and let y be a vertex not adjacent to x.

Since μ = 0, it follows from Equation (3.5) that λ = \frac{k−1}{2} ≥ 1. Thus the subgraphs spanned by N^{+}(x) and N^{−}(x) are regular tournaments of valency λ. Since μ = 0, y has no out-neighbour in N^{+}(x). But since Γ is connected, we may assume that y has an out-neighbour in N^{−}(x). Let U = N^{+}(y) ∩ N^{−}(x) and suppose that U ≠ N^{−}(x). Since N^{−}(x) is a regular tournament, there exist vertices u ∈ U and u′ ∈ N^{−}(x) \ U such that u′ → u. But y and u′ have a common out-neighbour and so they are adjacent. So we have y → u′, a contradiction. Thus N^{+}(y) = N^{−}(x).

Suppose there is another vertex y′ non-adjacent to x such that y′ has an out-neighbour in N^{−}(x). Then as above N^{+}(y′) = N^{−}(x). But then y and y′ have k common outneighbours, a contradiction to k > λ > μ = 0. Thus, as N^{−}(x) is regular of valency λ, any vertex in u ∈ N^{−}(x) has k − 1 − λ = λ in-neighbours in N^{+}(x). It also has λ out-neighbours in N^{+}(x), as x and u have λ common out-neighbours.

Now there is a vertex w ∈ N^{+}(x) such that w and y have a common out-neighbour in N^{−}(x). Thus w → y. As above, it follows that N^{−}(y) = N^{+}(x) and that any vertex in N^{+}(x) has λ out-neighbours and λ in-neighbours in N^{−}(x).

Since Γ is connected, it has vertex set {x, y} ∪ N^{+}(x) ∪ N^{−}(x). For every vertex there is a unique non-adjacent vertex. Thus Γ is a (\frac{v}{2}, 2)-team tournament. In fact, we have now proved that it is a doubly regular (\frac{v}{2}, 2)-team tournament with α = β = λ and γ = k. (Since x is an arbitrary vertex we need only consider paths of length 2 starting at x.) The statement now follows from Theorem 4.6, see Section 4. □

3.4. Association schemes and their relation graphs.

Definition 3.24. Let X be finite set and let {R_{0}, R_{1}, …, R_{d}} be a partition of X × X. Then we say that X = (X, {R_{0}, R_{1}, …, R_{d}}) is a d-class association scheme if the following conditions are satisfied:

• R_{0} = {(x, x) | x ∈ X},

• for each i ∈ {0, …, d} there exists i′ ∈ {0, …, d} such that

R_{i′} = {(x, y) | (y, x) ∈ R_{i}},

• for each triple (i, j, h), i, j, h ∈ {0, …, d}, there exists a number p_{ij}^{h} such that for all x, y ∈ X with (x, y) ∈ R_{h} there are exactly p_{ij}^{h} elements z ∈ X such that

(x, z) ∈ R_{i} and (z, y) ∈ R_{j}.

The binary relations R_{1}, …, R_{d} can be identified with (arc sets of) graphs on X. A relation R_{i} with i′ = i is an undirected graph and a relation R_{i} with i′ ≠ i is a directed (oriented) graph. If the graphs R_{1}, …, R_{d} are all connected then we say that X is primitive; otherwise it is imprimitive.

If i = i′ for all i then X is said to be symmetric; otherwise it is non-symmetric. For a symmetric 2-class association scheme the graph R_{1} is a strongly regular graph and R_{2} is its complement. Conversely, if Γ is a strongly regular graph then Γ and \overline{Γ} (i.e., E(Γ) and E(\overline{Γ})) form the relations of a symmetric 2-class association scheme. It is known that for an imprimitive symmetric 2-class association scheme, either R_{1} or R_{2} is isomorphic to m ∘ K_{r} for some m, r.

For a non-symmetric 2-class association scheme the graph R_{1} is a doubly regular tournament and conversely (see Lemma 3.3) for every doubly regular tournament R_{1} there is a non-symmetric 2-class association scheme (X, {R_{0}, R_{1}, R_{2}}). Every non-symmetric 2-class association scheme is primitive.

Let X = {x_{1}, …, x_{n}} be a finite set and let R_{0}, …, R_{d} be graphs (possibly with loops) with vertex set X. Let A_{i} be the adjacency matrix of R_{i}, for i = 0, …, d. Let A be the vector space spanned by A_{0}, …, A_{d}. Then {R_{0}, …, R_{d}} is a partition of X × X if and only if A_{0} + ⋯ + A_{d} = J and A_{i} ∘ A_{j} = 0 for all i ≠ j. The other conditions in Definition 3.24 are equivalent to

• A_{0} = I,
• A_{i}^{t} = A_{i′},
• A is closed under matrix multiplication and A_{i}A_{j} = ∑_{h} p_{ij}^{h}A_{h}.

Furthermore, if these conditions are satisfied then A is closed under the Schur-Hadamard product. The algebra A with two operations of multiplication, namely the usual matrix product and the Schur-Hadamard product, is called the adjacency algebra of the association scheme. The association scheme is symmetric if and only if A consists of symmetric matrices.

An association scheme X is called commutative if p_{ij}^{h} = p_{ji}^{h} for all i, j, h. Thus X is commutative if and only if A is commutative. The adjacency algebra of a commutative association scheme is usually called the Bose–Mesner algebra of this scheme. Every symmetric association scheme is commutative, for if A and B belong to an algebra of symmetric matrices then AB = A^{t}B^{t} = (BA)^{t} = BA. Higman [Hig75] proved that every d-class association scheme with d ≤ 4 is commutative.

For a commutative non-symmetric association scheme X = (X, {R_{0}, R_{1}, …, R_{d}}) it is known (see [BanI84, Remark in Section 2.2]) that a symmetric association scheme X̃, called the symmetrisation of X, can be constructed by replacing each pair R_{i}, R_{i′} (i ≠ i′) with R_{i} ∪ R_{i′}. The corresponding Bose–Mesner algebra is

Ã = {A ∈ A | A = A^{t}}.

Its basis consists of the matrices A_{i} where i = i′, and A_{i} + A_{i′} where i ≠ i′.

Let X be a non-symmetric 3-class association scheme. Then X consists of a pair of non-symmetric relations R_{1}, R_{2} and one symmetric relation R_{3} (in addition to R_{0}). By the theorem of Higman mentioned above, X is commutative. Thus the symmetrisation of X exists and is a 2-class association scheme with relations R_{1} ∪ R_{2} and R_{3}.

A non-symmetric association scheme X is imprimitive if and only if the symmetrisation X̃ is imprimitive. Now suppose that X is imprimitive. Then R_{1} is an orientation of either m ∘ K_{r} or \overline{m ∘ K_{r}}.

Proposition 3.25. R_{1} is an orientation of m∘K_{r} if and only if R_{1} consists of m disjoint doubly regular tournaments of order r.

Proof. Suppose first that R_{1} is an orientation of m ∘ K_{r}. Then R_{1} consists of m disjoint tournaments of order r, and R_{1} and each of the tournaments are regular of valency p_{12}^{0}. Let T be one of the components of R_{1}. Let (x, y) ∈ T. Then there are p_{11}^{1} paths of length 2 from x to y. Thus, according to Lemma 3.3, T is a doubly regular tournament.

Conversely, if R_{1} is a disjoint union of m doubly regular tournaments of order r (not necessarily isomorphic) then (V (R_{1}), {R_{0}, R_{1}, R_{2}, R_{3}}) is an imprimitive 3-class association scheme with R_{2} = R_{1}^{t} and R_{3} = \overline{R_{1} ∪ R_{2}}. □

We now consider the case where R_{1} is an orientation of \overline{m ∘ K_{r}}. First we give two types of examples.

Proposition 3.26. Let R_{1} be one of the graphs C_{r}(T) where r ≥ 2, or D(T) where T is a doubly regular tournament. Let R_{2} = R_{1}^{t} and R_{3} = \overline{R_{1} ∪ R_{2}}. Then

(V (R_{1}), {R_{0}, R_{1}, R_{2}, R_{3}})

is an imprimitive 3-class association scheme.

Proof. Let T be a doubly regular tournament on v vertices and with adjacency matrix A. Then C_{r}(T) has adjacency matrix A ⊗ J_{r}. The relations R_{2}, R_{3} and R_{0} in this case have adjacency matrices A^{t} ⊗ J_{r}, I_{v} ⊗ (J_{r} − I_{r}) and I_{v} ⊗ I_{r}. It follows from Lemma 2.1 and Lemma 3.3 that the set of linear combinations of these matrices is closed under multiplication.

Now suppose that D is the adjacency matrix of D(T) for some doubly regular tournament T. From Equations (3.2) and (3.6) we know that D^{2} = ℓD + ℓD^{t} = (D^{t})^{2} and DD^{t} = sI + ℓ(D + D^{t}) for some s = 2ℓ + 1. By Proposition 3.19, D^{t}D = DD^{t}. We also know that JD = DJ = JD^{t} = D^{t}J = sJ. It follows that any product of two matrices in B = {I, D, D^{t}, J − I − D − D^{t}} is a linear combination of matrices in B. Thus the relations with adjacency matrices in B form an imprimitive association scheme with 3 classes. □

In Section 5 we will continue our analysis of links between orientations of \overline{m ∘ K_{r}} and association schemes based on a characterisation of doubly regular (m, r)-team tournaments which will be achieved in the next section. We will also mention some constructions of doubly regular team tournaments with r > 2 in Section 5.2.

4. Characterisation of doubly regular (m, r)-team tournaments

4.1. Three types of graphs. Let Γ be a doubly regular (m, r)-team tournament and let α, β, γ be as in Definition 3.13. Let V (Γ) = V_{1} ∪ ⋯ ∪ V_{m} be the partition of the vertex set into m independent sets of size r.

In this section we prove that Γ is of one of three types:

Type I. C_{r}(T) for some doubly regular tournament T. Type II. Every vertex in V_{i} dominates exactly half of the vertices in each V_{j}, for j ≠ i. This

type includes D(T) for a doubly regular tournament T.

Type III. Every vertex in V_{i} dominates either all vertices of V_{j}, exactly half of the vertices in each V_{j} or none of the vertices of V_{j}, for j ≠ i, but Γ is not one of the above types. (No examples of this structure are known.)

More details about the structure of the last two types are given below.

For x ∈ V_{i}, let d_{j}(x) = |N^{+}(x) ∩ V_{j}| be the number of out-neighbours of x in V_{j}.

Lemma 4.1. Let x ∈ V_{i} and y ∈ V_{j} and suppose that (x, y) ∈ E(Γ). Then

d_{j}(x) − d_{i}(y) = β − α.

Proof. The vertex x has k − d_{j}(x) out-neighbours outside V_{j}. Exactly α of these outneighbours are in-neighbours of y and k − d_{j}(x) − α vertices are common out-neighbours of x and y. Similarly, y has k − d_{i}(y) out-neighbours outside V_{i}. Then β of these vertices are in-neighbours of x and k − d_{i}(y) − β vertices are common out-neighbours of x and y. Thus k − d_{j}(x) − α = k − d_{i}(y) − β. This proves the lemma. □

Lemma 4.2. For each pair (i, j), i ≠ j, either

1) there exists a constant c_{ij} such that d_{j}(x) = c_{ij} for every x ∈ V_{i} or else

2) V_{i} is partitioned into two nonempty sets V_{i} = V′_{i} ∪ V′′_{i} so that all arcs are directed from V′_{i} to V_{j} and from V_{j} to V′′_{i}.

Proof. Suppose that such a constant c_{ij} does not exist. Let x′, x′′ ∈ V_{i} be such that d_{j}(x′) ≠ d_{j}(x′′). Let y ∈ V_{j}. If (x′, y), (x′′, y) ∈ E(Γ) then

d_{j}(x′) − d_{i}(y) = β − α = d_{j}(x′′) − d_{i}(y),

i.e., d_{j}(x′) = d_{j}(x′′), a contradiction. If (y, x′), (y, x′′) ∈ E(Γ) then

d_{i}(y) − d_{j}(x′) = β − α = d_{i}(y) − d_{j}(x′′),

a contradiction. Thus V_{j} is partitioned into two sets V_{j} = V′_{j} ∪ V′′_{j} (one of the sets may be empty) so that V′_{j} is the set of out-neighbours of x′ in V_{j} and V′′_{j} is the set of out-neighbours of x′′ in V_{j}.

For every vertex x ∈ V_{i} with an out-neighbour in V′_{j}, d_{j}(x) = d_{j}(x′) ≠ d_{j}(x′′). Thus x has no out-neighbour in V′′_{j} and so the set of out-neighbours of x in V_{j} is exactly V′_{j}. Similarly, if x has an out-neighbour in V′′_{j} then the set of out-neighbours of x in V_{j} is V′′_{j}. If x has no out-neighbour in V_{j} then x has a common in-neighbour with either x′ or x′′, say with x′′. Then d_{j}(x′′) = d_{j}(x) = 0 and so the set of out-neighbours of x in V_{j} is V′′_{j} = ∅. Thus we also get a partition V_{i} = V′_{i} ∪ V′′_{i} so that the arcs between V_{i} and V_{j} are directed from V′_{i} to V′_{j}, from V′_{j} to V′′_{i}, from V′′_{i} to V′′_{j} and from V′′_{j} to V′_{i}. If either V′_{j} or V′′_{j} is empty then the second case of the lemma holds. So suppose that V′_{j} and V′′_{j} are both nonempty. Let y′ ∈ V′_{j} and y′′ ∈ V′′_{j}. From

|V′′_{j}| − |V′_{i}| = d_{j}(x′′) − d_{i}(y′′) = β − α = d_{i}(y′) − d_{j}(x′′) = |V′′_{i}| − |V′′_{j}|,

we get by adding |V′_{i}| + |V′′_{i}| = r = |V′_{j}| + |V′′_{j}| that d_{j}(x′′) = |V′′_{j}| = |V′_{j}| = d_{j}(x′), a contradiction. □

Theorem 4.3. Let Γ be a doubly regular (m, r)-team tournament. Then Γ satisfies one of the following:

Type I. β − α = r and Γ is isomorphic to C_{r}(T), for some doubly regular tournament T. Type II. β − α = 0, r is even and d_{i}(x) = \frac{r}{2} for all x ∉ V_{i}. Type III. β − α = \frac{r}{2} and for every pair \{i, j\} either V_{i} is partitioned into two sets V′_{i} and

V′′_{i} of size \frac{r}{2} so that all arcs between V_{i} and V_{j} are directed from V′_{i} to V_{j} and from V_{j} to V′′_{i}, or similarly with i and j interchanged.

Proof. Suppose that for some given pair (i, j), case (2) of Lemma 4.2 is satisfied. Let x′ ∈ V′_{i}, x′′ ∈ V′′_{i}, y ∈ V_{j}. By Lemma 4.1,

|V_{j}| − |V′′_{i}| = d_{j}(x′) − d_{i}(y) = β − α = d_{i}(y) − d_{j}(x′′) = |V′′_{i}|.

Thus |V′′_{i}| = \frac{1}{2}|V_{j}| = \frac{r}{2}, |V′_{i}| = \frac{r}{2} and β − α = \frac{r}{2}. A similar argument applies if the pair (j, i) satisfies case (2).

Suppose that there exist constants c_{ij} and c_{ji} such that d_{j}(x) = c_{ij} for every x ∈ V_{i} and d_{i}(x) = c_{ji} for every x ∈ V_{j}. Then there are two possibilities.

a) One of c_{ij}, c_{ji} is 0, suppose that c_{ji} = 0 and c_{ij} = r. Then β − α = c_{ij} − c_{ji} = r.

b) c_{ij} and c_{ji} are both positive, so that there exist arcs from V_{i} to V_{j} and arcs from V_{j} to V_{i}. Then c_{ij} − c_{ji} = β − α = c_{ji} − c_{ij}, i.e., c_{ij} = c_{ji} = \frac{r}{2} and β − α = 0.

Since the value of β − α is independent of the choice of {i, j}, we see that if case (2) of Lemma 4.2 is satisfied for at least one pair (i, j) then Γ is of Type III, and if b) is satisfied for some pair (i, j) then Γ is of Type II.

Suppose now that a) holds for every pair {i, j}. Then clearly Γ is isomorphic to C_{r}(T) for some regular tournament T. Suppose that (x, y) ∈ E(T) and that there are λ paths of length 2 from x to y in T. Then there are exactly rλ paths of length 2 between vertices in Γ in the cocliques corresponding to x and y. Thus λ = \frac{α}{r} is constant and so T is doubly regular. □

For doubly regular (m, r)-team tournaments of Type II and Type III it is possible to compute the parameters α, β, γ from m and r and to give some restrictions on m and r.

Theorem 4.4. Let Γ be a doubly regular (m, r)-team tournament of Type II. Then

1) α = β = \frac{(m−2)r}{4},
2) γ = \frac{(m−1)r^{2}}{4(r−1)} , and
3) r − 1 divides m − 1.

Proof. 1) Let x ∈ V_{1}. The number of directed paths of length 2 from x to a vertex y ∉ V_{1} is (m − 1)\frac{r}{2} · (m − 2)\frac{r}{2}. The number of such vertices y is (m − 1)r, so

α = β = \frac{(m − 1)\frac{r}{2}(m − 2)\frac{r}{2}}{(m − 1)r} = \frac{(m − 2)r}{4}.

2) The number of directed paths of length 2 from x to a vertex y ∈ V_{1} is (m − 1)\frac{r}{2} · \frac{r}{2}. The number of such vertices y is r − 1. Thus

γ = \frac{(m − 1)\frac{r}{2} \frac{r}{2}}{r − 1} = \frac{(m − 1)r^{2}}{4(r − 1)} .

3) Since γ is an integer and r and r − 1 are relatively prime, r − 1 divides m − 1. □

Theorem 4.5. Let Γ be a doubly regular (m, r)-team tournament of Type III. Then

1) α = \frac{(m−1)r}{4} − \frac{3r}{8},

2) β = \frac{(m−1)r}{4} + \frac{r}{8},

3) γ = \frac{(m−1)r^{2}}{8(r−1)} ,

4) for every i and for every x ∈ V_{i}, the sets \{j | d_{j}(x) = 0\}, \{j | d_{j}(x) = \frac{r}{2}\} and \{j | d_{j}(x) = r\} have cardinality \frac{m−1}{4}, \frac{m−1}{2} and \frac{m−1}{4}, respectively.

5) 8 divides r, and

6) 4(r − 1) divides m − 1.

Proof. For each pair {i, j}, either (i, j) or (j, i) satisfies case (2) of Lemma 4.2. Thus in the subgraph spanned by V_{i}∪V_{j} there are \frac{r^{3}}{4} directed paths of length 2 joining two nonadjacent vertices. The total number of directed paths of length 2 joining two nonadjacent vertices in Γ is \binom{m}{2} \frac{r^{3}}{4} . The number of ordered pairs of nonadjacent vertices is mr(r − 1). Thus γ = \frac{(m−1)r^{2}}{8(r−1)} as \binom{m}{2} \frac{r^{3}}{4} = mr(r − 1)γ. Since the number of directed paths of length 2 starting at a vertex x is independent of x, Γ satisfies property (4).

The number of arcs in Γ is mrk and the number of directed paths of length 2 is mrk^{2}. Thus

mrk^{2} − \binom{m}{2}\frac{r^{3}}{4} = mrk(α + β).

Since k = \frac{(m−1)r}{2},

\frac{(m − 1)^{2}r^{2}}{4} − \frac{(m − 1)r^{2}}{8} = \frac{(m − 1)r}{2}(α + β),

i.e.,

\frac{(m − 1)r}{2} − \frac{r}{4} = α + β.

Since β − α = \frac{r}{2}, we get the required solutions for α and β.

Since β and \frac{m−1}{4} are integers, \frac{r}{8} is also an integer.

Since γ is an integer and r − 1 and r are relatively prime, r − 1 divides m − 1. Since 4 divides m − 1 and r − 1 is odd, 4(r − 1) divides m − 1. □

Remark. It follows from 5) and 6) in Theorem 4.5 that the first feasible case is (m, r) = (29, 8). Suppose that a doubly regular (29, 8)-team tournament of Type III exists. Consider a fixed set V_{i}. For exactly half of the other sets V_{j}, say V_{j_{1}}, …, V_{j_{14}}, the set V_{i} is partitioned into two sets, say V′_{i}(j) and V′′_{i}(j), as in Lemma 4.2. It follows from the existence of the parameter γ that V′_{i}(j_{1}), …, V′_{i}(j_{14}) are the blocks of a 2-design with point set V_{i} and with parameters (v, b, r, k, λ) = (8, 14, 7, 4, 3). There are 4 non-isomorphic designs with these parameters; one of them is a Hadamard 3-design, see [BethJL85].

In order to construct a doubly regular (29, 8)-team tournament of Type III, we therefore need to put together 29 such designs (one for each V_{i}), in such a way that the parameters α and β also exist. It is not clear whether this is possible.

4.2. Doubly regular (m, 2)-team tournaments. We are mainly interested in the case r = 2. In this case Song [So95] proved that either m ≡ 0 mod 4 or m ≡ 3 mod 4.

Theorem 4.6. Let Γ be a doubly regular (m, 2)-team tournament. Then Γ is isomorphic to either C_{2}(T) or D(T) for some doubly regular tournament T.

Proof. Suppose that Γ is not isomorphic to C_{2}(T) for any doubly regular tournament T. Then, by Theorem 4.5, Γ is of Type II. By Theorem 4.3, every vertex in V_{i} has exactly one out-neighbour in V_{j}, i ≠ j. Thus the subgraph spanned by V_{i} ∪ V_{j} is a directed 4-cycle.

Let v_{0} be a vertex in Γ and v_{1}, … v_{k} be the out-neighbours of v_{0}. For i = 0, …, k let w_{i} be the unique vertex in Γ not adjacent to v_{i}. Then V (Γ) = {v_{0}, …, v_{k}, w_{0}, …, w_{k}} and these vertices are distinct.

Suppose that (v_{i}, v_{j}) ∈ E(Γ). Since the subgraph spanned by {v_{i}, v_{j}, w_{i}, w_{j}} is a 4-cycle, we also have (v_{j}, w_{i}), (w_{i}, w_{j}), (w_{j}, v_{i}) ∈ E(Γ). Thus Γ is isomorphic to D(T) where T is the tournament spanned by N^{+}(v_{0}). Since there are α paths of length 2 from v_{0} to v_{i}, v_{i} has in-valency α in T. Thus T is regular of valency α.

Suppose that (v_{i}, v_{j}) ∈ E(T). Let λ denote the number of paths of length 2 in T from v_{i} to v_{j}. Then v_{i} and v_{j} have α − 1 − λ common out-neighbours in T. Thus v_{j} has α − (α − 1 − λ) = λ + 1 out-neighbours in T which are in-neighbours of v_{i}, i.e., there are λ + 1 paths of length 2 in T from v_{j} to v_{i}.

Any path of length 2 from v_{i} to v_{j} contained in Γ but not in T has the form v_{i}w_{ℓ}v_{j}. But v_{i}w_{ℓ}v_{j} is a directed path if and only if v_{j}v_{ℓ}v_{i} is a directed path from v_{j} to v_{i}. Thus Γ contains λ + (λ + 1) paths of length 2 from v_{i} to v_{j}. Since this number is α, λ = \frac{α−1}{2} is constant, and so T is doubly regular. □

Remarks. 1. In the definition of D(T) (Definition 3.15) the vertex v_{0} plays a special role. However, the above proof shows that if T is a doubly regular tournament then any vertex in D(T) can be chosen to play this role. Thus for any vertex x, the subgraph spanned by N^{+}(x) is a doubly regular tournament. This tournament need not be isomorphic to N^{+}(v_{0}), but Hadamard matrices constructed from them as in Theorem 3.12 are equivalent. The relationship between the tournaments N^{+}(v_{0}) and N^{+}(x) was investigated in [Jør94].

2. Due to the existence of infinitely many doubly regular tournaments, we obtain infinitely many examples of doubly regular (m, r)-team tournaments.

5. Equivalence of main structures

5.1. Simple corollaries. We will begin with a simple corollary of some results which were obtained in previous sections.

Corollary 5.1. Every doubly regular (m, r)-team tournament with r = 2 is a relation of an imprimitive 3-class association scheme.

Proof. This follows from Theorem 4.6 and Proposition 3.26. □

Proposition 5.2. A doubly regular (m, r)-team tournament of Type III is not a relation of a 3-class association scheme.

Proof. Suppose that R_{1} is a doubly regular (m, r)-team tournament of Type III and that R_{0}, R_{1}, R_{2}, R_{3} are the relations of a 3-class association scheme, where R_{2} = R_{1}^{t}. Then R_{3} is an undirected graph with components V_{1}, …, V_{m}, each of which spans a complete graph. Let (x, y) ∈ R_{1}. Then there exist i ≠ j such that x ∈ V_{i} and y ∈ V_{j}. Then in R_{1}, x has p_{13}^{1} + p_{10}^{1} out-neighbours in V_{j}. But by Theorem 4.5, this number is not a constant. □

Proposition 5.3. Let (X, {R_{0}, R_{1}, R_{2}, R_{3}}) be a non-symmetric imprimitive 3-class association scheme such that R_{1} and R_{2} are directed graphs and R_{3} is a disconnected undirected graph. Then R_{1} is a doubly regular (m, r)-team tournament of Type I or Type II for some m, r ∈ ℕ.

Proof. Let A_{0}, A_{1}, A_{2}, A_{3} be the adjacency matrices of R_{0}, R_{1}, R_{2}, R_{3}. Then A_{1}^{2} = p_{11}^{0}A_{0} + p_{11}^{1}A_{1} + p_{11}^{2}A_{2} + p_{11}^{3}A_{3} = p_{11}^{1}A_{1} + p_{11}^{2}A_{1}^{t} + p_{11}^{3}(J − I − A_{1} − A_{1}^{t}), as p_{11}^{0} = 0. Thus R_{1} is a doubly regular team tournament. By Proposition 5.2, it is of Type I or Type II. □

Therefore, the imprimitive non-symmetric 3-class association schemes for which R_{1} is an orientation of \overline{m ∘ K_{r}} for r = 2 are characterized by R_{1} being isomorphic to either C_{2}(T) or D(T) for some doubly regular tournament T. For r ≥ 3, we have the following theorem of Goldbach and Claasen [GolC96]. For completeness we give an alternative proof of this statement here.

Theorem 5.4. Let (X, {R_{0}, R_{1}, R_{2}, R_{3}}) be a non-symmetric imprimitive 3-class association scheme such that R_{1} is an orientation of \overline{m ∘ K_{r}}. Then either R_{1} is isomorphic to C_{r}(T) for some doubly regular tournament T, or else

• r − 1 divides m − 1 and

• r and m are both even.

Proof. If R_{1} is not isomorphic to C_{r}(T) then by Proposition 5.3, R_{1} is a doubly regular (m, r)-team tournament of Type II. It follows from Theorem 4.3 and Theorem 4.4 that r is even and that r − 1 divides m − 1. In Corollary 5.8 below, it will be proved that m is even. □

We have proved above that a non-symmetric relation of an imprimitive 3-class association scheme is a doubly regular team tournament of Type I or Type II. The converse is also true. The following theorem is the corresponding formal claim.

Theorem 5.5. Let R_{1} be a doubly regular (m, r)-team tournament of Type I or Type II. Let R_{2} = R_{1}^{t} and R_{3} = \overline{R_{1} ∪ R_{2}}. Then (V (R_{1}), \{R_{0}, R_{1}, R_{2}, R_{3}\}) is an imprimitive 3-class association scheme.

We know from Proposition 3.26 that Theorem 5.5 is true for doubly regular (m, r)-team tournaments of Type I. In order to prove the theorem for doubly regular (m, r)-team tournaments of Type II we need the following lemma.

Lemma 5.6. Let A be the adjacency matrix of a doubly regular (m, r)-team tournament Γ of Type II. Then A is normal.

Proof. We must prove that AA^{t} = A^{t}A, i.e., that for every pair x, y of vertices, the number of common out-neighbours is equal to the number of common in-neighbours. Since Γ is regular, this is true for x = y. Suppose that x and y are distinct. By Theorem 4.3, x and y both have exactly \frac{r}{2} out-neighbours in each V_{i}, where x, y ∉ V_{i}. Thus for each V_{i} the number of common out-neighbours of x and y in V_{i} is equal to the number of common in-neighbours of x and y (these are the vertices in V_{i} that are out-neighbours of neither x nor y.) □

It follows from the classical spectral theorem for normal matrices that A has an orthogonal diagonalisation. Let λ_{0}, …, λ_{s} be the distinct eigenvalues. Let E_{0}, …, E_{s} be the orthogonal projections onto the corresponding eigenspaces. Then

A = ∑_{i=0}^{s} λ_{i}E_{i},

and I = ∑_{i=0}^{s} E_{i}. Then

A^{2} = ∑_{i=0}^{s} λ_{i}^{2}E_{i},

and since orthogonal projections are self-adjoint,

A^{t} = ∑_{i=0}^{s} \overline{λ_{i}}E_{i}.

We may assume that λ_{0} = k = \frac{(m−1)r}{2}. Then J = mrE_{0}.

Lemma 5.7. Let Γ be a doubly regular (m, r)-team tournament of Type II. Then the adjacency matrix A of Γ has exactly four distinct eigenvalues.

Proof. If we use the above expressions for A, A^{2} and A^{t} in the equation

A^{2} = αA + βA^{t} + γ(J − I − A − A^{t})

and multiply by E_{j}, j ≠ 0, then we get

λ_{j}^{2} = αλ_{j} + β\overline{λ_{j}} + γ(−1 − λ_{j} − \overline{λ_{j}}).

Let λ_{j} = a + bi, where a and b are real. Since β = α,

a^{2} − b^{2} + 2abi = 2aα + γ(−1 − 2a).

Since the imaginary part of this is 2ab = 0, either b = 0 (and λ_{j} is real) or a = 0 and b^{2} = γ.

The adjacency matrix of \overline{m ∘ K_{r}} is

A + A^{t} = ∑_{j=0}^{s}(λ_{j} + \overline{λ_{j}})E_{j}.

Thus λ_{j} + \overline{λ_{j}} = 2a is one of the three eigenvalues 2k = (m − 1)r, 0 or −r of \overline{m ∘ K_{r}}. Thus the eigenvalues of Γ are k, −\frac{r}{2}, ±i\sqrt{γ}. □

Corollary 5.8. Let Γ be a doubly regular (m, r)-team tournament of Type II. Then m is even.

Proof. Since the multiplicity of 0 as an eigenvalue of \overline{m ∘ K_{r}} is m(r − 1), the eigenvalues ±i\sqrt{γ} of Γ both have multiplicity \frac{m(r−1)}{2}, and so m must be even. □

Proof of Theorem 5.5. Let A be the adjacency matrix of R_{1}. By the above lemma, A has four eigenvalues λ_{0}, …, λ_{3} with corresponding orthogonal projections E_{0}, …, E_{3}. Let A denote the set of matrices that are linear combinations of E_{0}, …, E_{3}. Then A is a four-dimensional algebra closed under matrix multiplication.

The set B = {I, A, A^{t}, J − I − A − A^{t}} consists of four linearly independent matrices, and by the above remarks they are contained in A. Thus B is a basis of A and any product of matrices from B is a linear combination of elements of B. The matrices in B are the adjacency matrices of relations R_{0}, R_{1}, R_{2}, R_{3} of an imprimitive 3-class association scheme. □

5.2. Type II doubly regular (m, r)-team tournaments with r > 2. We have seen above that, whenever r and m are positive even integers such that r − 1 divides m − 1, it is possible that a doubly regular (m, r)-team tournament of Type II or equivalently an imprimitive non-symmetric 3-class association scheme exists. For many such pairs (m, r) existence is still open. However, there are also some existence results, in particular when r = m and m ≡ 0 mod 4. The constructions are related to a certain type of Hadamard matrices.

Definition 5.9. A Hadamard matrix H of order m^{2} is said to be a Bush-type Hadamard matrix if it is a block matrix with m × m blocks H_{ij} of size m × m such that H_{ii} = J_{m} and H_{ij}J_{m} = J_{m}H_{ij} = 0 for all i ≠ j.

We say that a Bush-type Hadamard matrix is skew if H_{ij} = −(H_{ji})^{t} for all i ≠ j.

[GolC98] proved that these Hadamard matrices are equivalent to the association schemes considered here, see also [Jør09].

Theorem 5.10. A doubly regular (m, r)-team tournament of Type II with r = m is equivalent to a skew Bush-type Hadamard matrix of order m^{2}.

Bush-type Hadamard matrices of order m^{2} and thus doubly regular (m, m)-team tournaments where constructed by Ionin and Kharaghani for many values of m where m ≡ 0 mod 4.

Theorem 5.11 ([IonK03]). If there exists a Hadamard matrix of order m then there exists a skew Bush-type Hadamard matrix of order m^{2}.

Davis and Polhill found a family of highly symmetric doubly regular team tournaments.

Theorem 5.12 ([DavP10]). For every s ≥ 2 there exists a Cayley graph over (ℤ_{4})^{s} which is a doubly regular (m, r)-team tournament of Type II with m = r = 2^{s} and with automorphism group of rank 4, i.e., the automorphism group acts transitively on vertices, on directed edges, and on ordered pairs of nonadjacent vertices.

Example 5.13. The Cayley graph Γ = Cay(ℤ_{4} × ℤ_{4}, X) with connection set

X = {(0, 1), (1, 0), (1, 1), (1, 2), (3, 1), (2, 3)}

is a doubly regular (4, 4)-team tournament with α = β = 2 and γ = 4. The four independent sets of 4 vertices are the cosets of the subgroup {(0, 0), (0, 2), (2, 0), (2, 2)}. Γ has automorphism group of rank 4.

For m ≡ 2 mod 4 not much is known, but in [Jør09] it was shown that there are at least four doubly regular (6, 6)-team tournaments.

Also for 2 < r < m, most feasible cases are open, but in [Jør10] 40 non-isomorphic doubly regular (16, 4)-team tournaments were constructed as Cayley graphs.

In the remaining sections of this paper we will focus on theory related to the case r = 2.

6. Vertex transitive doubly regular team tournaments

In [Jør94] it was proved that D(T) is vertex transitive in the two cases where T is the Paley tournament P_{q} (cf. Theorem 3.7), and where T is the Szekeres tournament Sz_{q}. We now consider groups acting transitively on a graph D(T) for some doubly regular tournament T. It is a well known fact that a tournament does not have any automorphism of order 2. A modification of the proof of this shows that D(T) has only one automorphism of order 2.

Lemma 6.1. Let Γ be the graph D(T) for some tournament T. Then the automorphism group of Γ contains a unique involution ϕ. This involution ϕ maps a vertex x to the unique vertex in Γ nonadjacent to x.

Proof. It is easy to verify that ϕ is an automorphism. Let ψ be an involutory automorphism of Γ. If for some vertex x, (x, ψ(x)) ∈ E(Γ) then (ψ(x), ψ^{2}(x)) = (ψ(x), x) ∈ E(Γ), a contradiction. Similarly, it is impossible that (ψ(x), x) ∈ E(Γ). If ψ(x) = x then for any vertex y ∈ N^{+}(x) we have ψ(y) = y, as N^{+}(x) is a tournament. Then it follows from the structure of Γ that ψ(y) = y for every vertex y ∈ V (Γ). Thus for every vertex x, ψ(x) is the unique vertex not adjacent to x, and so ψ = ϕ. □

Lemma 6.2. Let G be a group of automorphisms of Γ = D(T) for some doubly regular tournament T, and suppose that G has order a power of 2. Then the action of G on V (Γ) is semiregular.

Proof. Let x ∈ V (Γ). By Lemma 6.1, G_{x} has odd order, but the order of G_{x} is a power of 2. Thus |G_{x}| = 1. □

We wish to prove that the Sylow 2-subgroups of the automorphism group of a vertex transitive graph D(T) are generalised quaternion groups. Ito [Ito94] showed that the Sylow 2–subgroups of a Hadamard group cannot be cyclic (see Section 8 below). We prove a similar theorem for the automorphism group of D(T), but we do not require that the graph is a Cayley graph. First we need a few lemmas.

Lemma 6.3. Let Γ be a directed graph with vertex set {x_{0}, …, x_{4m−1}} such that

• the permutation g = (x_{0}, …, x_{4m−1}) is an automorphism;

• the pairs of non-adjacent vertices are the pairs {x_{i}, x_{i+2m}}, for i = 0, …, 2m − 1; and

• if x_{0} → x_{ℓ} then x_{ℓ} → x_{2m}.

Then the number of common out-neighbours of x_{0} and x_{1} in Γ is even.

Proof. If x_{0} → x_{ℓ} then, since g^{2m} is an automorphism, x_{0} → x_{ℓ} → x_{2m} → x_{2m+ℓ} → x_{0}, and by applying g^{−ℓ} to this we get x_{0} → x_{2m−ℓ} → x_{2m} → x_{4m−ℓ} → x_{0}.

The proof is by induction on the number s of out-neighbours of x_{0} in {x_{2m+1}, …, x_{4m−1}}. If s = 0 then N^{+}(x_{0}) = {x_{1}, …, x_{2m−1}}, and so N^{+}(x_{1}) = {x_{2}, …, x_{2m}}. Thus x_{0} and x_{1} have 2m − 2 common out-neighbours.

For the induction step, suppose that for some ℓ such that 1 ≤ ℓ ≤ m the arcs in the set B = {x_{i} → x_{i+ℓ}, x_{i} → x_{i+2m−ℓ} | i = 0, … 4m − 1} are reversed.

Suppose first that 1 < ℓ < m. If x_{0} → x_{ℓ−1} and thus x_{1} → x_{ℓ}, x_{0} → x_{2m−ℓ+1}, x_{0} ← x_{−ℓ+1} and x_{1} ← x_{2m+ℓ}, then by reversal of arcs in B the vertices x_{ℓ} and x_{2m−ℓ+1} are removed from the set of common out-neighbours of x_{0} and x_{1}. If x_{0} ← x_{ℓ−1} then x_{−ℓ+1} and x_{2m+ℓ} will be new common out-neighbours of x_{0} and x_{1} after reversal of arcs in B. If x_{0} → x_{ℓ+1} and thus x_{1} → x_{2m−ℓ}, x_{0} ← x_{2m+ℓ+1} and x_{1} ← x_{−ℓ}, then reversal will remove x_{ℓ+1} and x_{2m−ℓ} from the list of common out-neighbours, but if x_{0} ← x_{ℓ+1} then x_{2m+ℓ+1} and x_{−ℓ} will be new common out-neighbours. Thus the number of common out-neighbours of x_{0} and x_{1} will increase by ±2 ± 2.

The case ℓ = 1 is essentially the same as the above except that arcs x_{0} → x_{ℓ−1} and x_{0} → x_{2m−ℓ+1} cannot exist. The number of common out-neighbours will increase by ±2.

In the case ℓ = m, x_{0} → x_{ℓ−1} exists if and only if x_{0} → x_{ℓ+1} exists. The number of common out-neighbours will increase by ±2.

In each case the number of common out-neighbours of x_{0} and x_{1} will remain even. □

Lemma 6.4. Let Γ be a directed graph with vertex set {x_{0}, …, x_{4m−1}, v_{0}, …, v_{4m−1}} such that

• the permutation g = (x_{0}, …, x_{4m−1})(v_{0}, …, v_{4m−1}) is an automorphism,
• for each i = 0, …, 2m − 1, either x_{0} → v_{i} or x_{0} ← v_{i}, and
• if x_{0} → v_{l} then v_{l+2m} → x_{0}.

Then the number of common out-neighbours of x_{0} and x_{1} in D = {v_{0}, …, v_{4m−1}} is odd.

Proof. The proof is by induction on the number s of out-neighbours of x_{0} in {v_{2m}, …, v_{4m−1}}.

If s = 0 then x_{0} is adjacent to v_{0}, …, v_{2m−1}, and since g is an automorphism, x_{1} is adjacent to v_{1}, …, v_{2m}. Thus the number of common out-neighbours of x_{0} and x_{1} in D is 2m − 1.

For the induction step, suppose that for some l, the arcs x_{i} → v_{i+l} and thus v_{i+l+2m} → x_{i}, i = 0, …, 4m − 1, are reversed. This reversal affects only common out-neighbours in {v_{l}, v_{l+1}, v_{l+2m}, v_{l+2m+1}}. Thus the number of common out-neighbours of x_{0} and x_{1} in D increases by 2, 0 or −2, if x_{0} was adjacent to none of x_{l−1} or x_{l+1}, to exactly one of them, or to both of them, respectively.

Thus x_{0} and x_{1} always have an odd number of common out-neighbours in D. □

Lemma 6.5. Let Γ be isomorphic to D(T) for some doubly regular tournament T. Let g be a semiregular automorphism of Γ. Then the number of orbits of g is even.

Proof. Suppose that the number of orbits is odd. Then 8 divides the order of g. Let the order of g be 4m. Then g^{2m} is the unique automorphism of order 2. Let x_{0} ∈ V (Γ) and let C be the orbit containing x_{0}. Let x_{i} = x_{0}^{g^{i}}. Then the subgraph of Γ spanned by C satisfies the conditions in Lemma 6.3. Thus the number of common out-neighbours of x_{0} and x_{1} in C is even.

Let D = {v_{0}, …, v_{4m−1}} be any other orbit of g with v_{i} = v_{0}^{g^{i}}. The subgraph spanned by C and D satisfies the conditions of Lemma 6.4. Thus the number of common outneighbours of x_{0} and x_{1} in D is odd. Since there is an even number of orbits different from C, x_{0} and x_{1} have an even number of common out-neighbours outside C and thus an even number of common out-neighbours in Γ. However, the number of common out-neighbours of two adjacent vertices in D(T) is odd, a contradiction. □

Theorem 6.6. Suppose that for some doubly regular tournament T, the graph Γ = D(T) is vertex transitive and has automorphism group G. Then a Sylow 2-subgroup S of G is a generalised quaternion group of order 2^{n}, where 2^{n} is the highest power of 2 that divides the order of Γ.

Proof. Since Γ is vertex transitive the order of G is divisible by the order of Γ and thus by 2^{n}. It follows that the order of S is at least 2^{n}. Since the action of S on V (Γ) is semiregular, the order of S is not divisible by 2^{n+1}. Thus |S| = 2^{n}.

Since G and thus S has a unique involution and the order of S is a power of 2, S is either a cyclic group or a generalised quaternion group, see [Gor68, Theorem 5.4.10(ii)] or [Hup67, Satz III.8.2(b)]. Since S is semiregular, the number of orbits under the action of S is |Γ|/2^{n}, which is odd. Thus by Lemma 6.5, S cannot be cyclic. □

Corollary 6.7. Suppose that for some doubly regular tournament T, the graph Γ = D(T) is vertex transitive and has order 2^{n}. Then Γ is a Cayley graph for the generalised quaternion group of order 2^{n}.

Proof. By Theorem 6.6, a Sylow 2-subgroup S of the automorphism group of Γ is a generalised quaternion group of order 2^{n}. By Lemma 6.2, S is semiregular and thus regular. □

In the next section we will investigate the possibilities for a graph Γ satisfying the hypotheses of Corollary 6.7.

7. Cayley graphs and group rings

Many normally regular digraphs arise from Cayley graphs, group rings and difference sets. We consider first under what conditions on the connection set S ⊂ G the Cayley graph Cay(G, S) becomes a normally regular digraph.

Proposition 7.1. Let G be a group with identity 1 and let S ⊂ G. Let S^{(−1)} denote the set {s^{−1} | s ∈ S}. Let Γ be Cay(G, S). Then Γ is a normally regular digraph with parameters (|G|, |S|, λ, μ) if and only if S ∩ S^{(−1)} = ∅ and for any g ∈ G the number of pairs (s, t) ∈ S × S such that st^{−1} = g is

\begin{cases}|S|, & if g = 1, \\ λ, & if g ∈ S ∪ S^{(−1)}, \\ μ, & otherwise. \end{cases}

Proof. The condition S ∩S^{(−1)} = ∅ ensures that the graph does not have undirected edges or loops. Let x and y be distinct vertices in Γ. There exists a unique g ∈ G such that xg = y. Then x → y if g ∈ S and y → x if g ∈ S^{(−1)}. Let z be a vertex in Γ. Then x → z if z = xs for some s ∈ S, and y → z if z = yt for some t ∈ S. Thus z is a common out-neighbour of x and y if and only if xs = yt = xgt. This is equivalent to g = st^{−1}, and so the number of common out-neighbours of x and y is equal to the number of pairs (s, t) ∈ S × S such that g = st^{−1}. □

For a (multiplicative) group G, the group ring ℤG is the set of formal sums ∑_{g∈G} c_{g}g,

where c_{g} ∈ ℤ. Then ℤG is a ring with sum

(∑_{g∈G} c_{g}g) + (∑_{g∈G} d_{g}g) = ∑_{g∈G}(c_{g} + d_{g})g

and product

(∑_{g∈G} c_{g}g) · (∑_{g∈G} d_{g}g) = ∑_{g∈G} (∑_{h∈G} c_{h}d_{h^{−1}g}) g.

For a set S ⊆ G we define \underline{S} = ∑_{g∈S} g ∈ ℤG. We write \underline{\{g\}} as g.

The conditions in Proposition 7.1 can be reformulated in terms of the group ring.

Corollary 7.2. Cay(G, S) is a normally regular digraph with parameters (v, k, λ, μ) where v = |G| and k = |S| if and only if

• S ∩ S^{(−1)} = ∅, and

• \underline{S} · \underline{S^{(−1)}} = k1 + λ(\underline{S} + \underline{S^{(−1)}}) + μ(\underline{G} − \underline{S} − \underline{S^{(−1)}} − 1) in the group ring ℤG.

For the particular case μ = 0, we get the following corollary.

Corollary 7.3. Cay(G, S) is isomorphic to D(T) for some doubly regular tournament T if and only if

• |G| = 4λ + 4 and |S| = 2λ + 1, for some λ,

• S ∩ S^{(−1)} = ∅, and

• \underline{S} · \underline{S^{(−1)}} = (2λ + 1)1 + λ(\underline{S} + \underline{S^{(−1)}}).

The condition S ∩ S^{(−1)} = ∅ implies that 1 ∉ S. We will next consider a property of sets satisfied by S ∪ {1}.

Definition 7.4. Let G be a group of order mn. Let N be a subgroup of G of index m. A subset D ⊂ G is said to be a relative (m, n, k, λ) difference set with forbidden subgroup N if |D| = k and for any g ∈ G the number of pairs (s, t) ∈ D × D such that g = st^{−1} is exactly

\begin{cases}k, & if g = 1, \\ 0, & if g ∈ N, g ≠ 1, \\ λ, & if g ∉ N. \end{cases}

Example 7.5. Let G = ℤ_{2}^{3} be the elementary abelian group of order 8 and let N = {(0, 0, 0), (1, 1, 1)}. Then D = {(0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1)} is a relative (4, 2, 4, 2) difference set. However, S = D\{(0, 0, 0)} does not satisfy the condition S ∩S^{(−1)} = ∅. In Example 7.9 we present another relative difference set with the same parameters satisfying all the conditions in Corollary 7.3.

It is usually assumed that N is a normal subgroup. Since N is a forbidden subgroup, D has at most one element in each (right) coset of N. We consider the case where m = k; that is, D has exactly one element in each coset of N.

The conditions in the definition of relative difference sets can be stated in terms of the group ring.

Lemma 7.6. Let N < G be as in the above definition. Then a subset D ⊂ G with |D| = k is a relative difference set if and only if

\underline{D} · \underline{D^{(−1)}} = k1 + λ(\underline{G} − \underline{N}).

In the next lemma we see that from one relative difference set several new relative difference sets can be constructed by shifting D.

Lemma 7.7. If D ⊂ G is a relative difference set then for any g ∈ G, Dg = {dg | d ∈ D} is a relative difference set with the same forbidden subgroup and the same parameters.

Proof.

\underline{Dg} · \underline{(Dg)^{(−1)}} = \underline{Dg} · \underline{g^{−1}D^{(−1)}} = \underline{D} · \underline{D^{(−1)}}.
□

In Lemma 6.1 we have observed that for any tournament T the graph D(T) has a unique automorphism of order 2. This automorphism is forbidden as a “difference” of elements in the connection set if D(T) is a Cayley graph.

Proposition 7.8. Suppose that Γ = Cay(G, S) is isomorphic to D(T) for some doubly regular tournament T and |G| = 4λ+4. Then S ∪{1} is a relative (2n, 2, 2n, n) difference set in G with forbidden subgroup N = ⟨ϕ⟩, where ϕ is the unique involutory automorphism of Γ and n = λ + 1.

Proof. From Corollary 7.3 we get

\underline{(S ∪ \{1\})} · \underline{(S ∪ \{1\})^{−1}} = \underline{S} · \underline{S^{(−1)}} + \underline{S} + \underline{S^{(−1)}} + 1 =
(2λ + 2)1 + (λ + 1)(\underline{S} + \underline{S^{(−1)}}) = 2n · 1 + n\underline{(S ∪ S^{(−1)})}.

By Lemma 6.1, S ∪ S^{(−1)} = G \ N. Thus we have

\underline{(S ∪ \{1\})} · \underline{(S ∪ \{1\})^{−1}} = 2n · 1 + n(\underline{G} − \underline{N}).
□

Example 7.9. The smallest, almost trivial, example of a doubly regular tournament is, clearly, a directed triangle Δ. It is clear that D(Δ) has 8 vertices. We are in a position to represent D(Δ) as a Cayley graph. For this purpose, let us consider the well-known quaternion group Q = {1, −1, i, j, k, −i, −j, −k} with the usual multiplication table. Let S = {i, j, k}. Then the Cayley graph Γ = Cay(Q, S) satisfies all the requirements of Proposition 7.8. Indeed,

\underline{\{1, i, j, k\}} · \underline{\{1, −i, −j, −k\}} = 4 · \underline{\{1\}} + 2 · \underline{\{i, j, k, −i, −j, −k\}}.

This implies that the set {1, i, j, k} is a relative (4, 2, 4, 2) difference set in Q with forbidden subgroup N = ⟨−1⟩ = {−1, 1}. Here −1 is the unique involutory automorphism of Γ (provided that we regard Q as a regular group, acting on the vertices of Γ).

Suppose that D ⊂ G is a relative (2n, 2, 2n, n) difference set. Then, by shifting if necessary, we may assume that 1 ∈ D.

Proposition 7.10. If D ⊂ G is a relative (2n, 2, 2n, n) difference set with forbidden subgroup N = ⟨ϕ⟩ such that D ∩ D^{(−1)} = {1}, then Cay(G, D \ {1}) is isomorphic to D(T) for some doubly regular tournament T.

Proof. Let S = D \ \{1\}. Since D ∩ D^{(−1)} = \{1\}, we get S ∩ S^{(−1)} = ∅, \underline{D} + \underline{D^{(−1)}} = \underline{G} − ϕ + 1 = \underline{G} − \underline{N} + 2 · 1 and S ∪ S^{(−1)} = G \ N. Thus \underline{S} · \underline{S^{(−1)}} = (\underline{D} − 1) · (\underline{D^{(−1)}} − 1) = \underline{D}·\underline{D^{(−1)}}−\underline{D}−\underline{D^{(−1)}}+1 = 2n·1+n(\underline{G}−\underline{N})−(\underline{G}−\underline{N} +2)+1 = (n−1)(\underline{G}−\underline{N})+(2n−1)·1 = (n − 1)(\underline{S} + \underline{S^{(−1)}}) + (2n − 1) · 1. If we let λ = n − 1 then we get all the conditions in Corollary 7.3. □

8. Ito’s Conjecture and S-rings over dicyclic groups

In [Ito94], N. Ito proposed the construction of Hadamard matrices from relative difference sets, and he introduced the following definition.

Definition 8.1. A group of order 4n is called a Hadamard group if it contains a relative (2n, 2, 2n, n) difference set, relative to some normal subgroup of order 2.

Ito [Ito94] proved that the existence of a Hadamard group of order 4n implies the existence of a Hadamard matrix of order 2n.

Theorem 8.2. Let G be a group of order 4n and let N = ⟨u⟩ be a normal subgroup of order 2. Let D ⊂ G be a relative (2n, 2, 2n, n) difference set. Let a_{1}, …, a_{2n} be representatives of the cosets of N. Let H = (h_{ij}) be the 2n × 2n matrix with

h_{ij} = \begin{cases}−1, & if a_{j} ∈ a_{i}D, \\ 1, & if ua_{j} ∈ a_{i}D. \end{cases}

Then H is a Hadamard matrix.

Proof. First, we must prove that h_{ij} is well defined for every i, j, i.e., that |{a_{j}, ua_{j}} ∩ a_{i}D| = 1. Suppose that {a_{j}, ua_{j}} ⊂ a_{i}D. Then there exist d_{1}, d_{2} ∈ D such that a_{j} = a_{i}d_{1} and ua_{j} = a_{i}d_{2}, and so d_{1}d_{2}^{−1} = (a_{i}^{−1}a_{j})(a_{i}^{−1}ua_{j})^{−1} = a_{i}^{−1}a_{j}a_{j}^{−1}u^{−1}a_{i} = a_{i}^{−1}ua_{i} = u as N is a normal subgroup. But this is a contradiction, as N is the forbidden subgroup. Thus |{a_{j}, ua_{j}} ∩ a_{i}D| ≤ 1. Since a_{i}D has cardinality 2n and there are 2n sets {a_{j}, ua_{j}}, |{a_{j}, ua_{j}} ∩ a_{i}D| = 1 for every i, j.

Since H has entries ±1, we need only to prove that HH^{t} = 2nI. For 1 ≤ i, ℓ ≤ n, i ≠ ℓ, the cardinality of the set a_{i}D ∩ a_{ℓ}D is

|{g ∈ G : g = a_{i}d_{1} and g = a_{ℓ}d_{2}, for some d_{1}, d_{2} ∈ D}|
= |{(d_{1}, d_{2}) ∈ D × D : a_{i}d_{1} = a_{ℓ}d_{2}}|
= |{(d_{1}, d_{2}) ∈ D × D : d_{1}d_{2}^{−1} = a_{i}^{−1}a_{ℓ}}|
= n,

as D is a relative (2n, 2, 2n, n) difference set and a_{i}^{−1}a_{ℓ} ∉ N. The number of columns j such that h_{ij} = h_{ℓj} = −1 is |{j | a_{j} ∈ a_{i}D ∩ a_{ℓ}D}|, and the number of columns j where h_{ij} = h_{ℓj} = 1 is |{j | ua_{j} ∈ a_{i}D ∩ a_{ℓ}D}|. Since G = {a_{1}, …, a_{2n}, ua_{1}, …, ua_{2n}}, the number of values of j where h_{ij} and h_{ℓj} are equal is |a_{i}D ∩ a_{ℓ}D| = n. Also h_{ij} and h_{ℓj} are different for the remaining n values of j. Thus the dot product of rows i and ℓ is 0. □

Example 8.3. Consider the relative difference set from Example 7.5 and let a_{1} = (0, 0, 0), a_{2} = (1, 0, 0), a_{3} = (0, 1, 0) and a_{4} = (0, 0, 1) be representatives of the cosets of N. Then the Hadamard matrix constructed in Theorem 8.2 is

[ \begin{matrix}−1 & −1 & −1 & −1 \\ −1 & −1 & 1 & 1 \\ −1 & 1 & −1 & 1 \\ −1 & 1 & 1 & −1 \end{matrix} ] .

If we use the relative difference set from Example 7.9 and let a_{1} = 1, a_{2} = i, a_{3} = j and a_{4} = k be representatives of the cosets of N then we get the following skew Hadamard matrix

[ \begin{matrix}−1 & −1 & −1 & −1 \\ 1 & −1 & 1 & −1 \\ 1 & −1 & −1 & 1 \\ 1 & 1 & −1 & −1 \end{matrix} ] .

Ito [Ito94] also proved that the Sylow 2-subgroups of a Hadamard group are not cyclic or dihedral. In [Ito97] he conjectured that every dicyclic group of order 8t, for some t, is a Hadamard group. By Theorem 8.2 this would imply the Hadamard matrix conjecture. Theorem 8.7 below shows that the conjecture is true for infinitely many values of t. Schmidt [Sch99] proved that the conjecture is true for t ≤ 46. Ito [Ito94] also investigated conditions for the constructed Hadamard matrix to be skew.

Theorem 8.4. Let G be a Hadamard group of order 4n and let N = ⟨u⟩ be a normal subgroup of order 2. Let D ⊂ G be a relative (2n, 2, 2n, n) difference set and let H = (h_{ij}) be the Hadamard matrix constructed from D in Theorem 8.2. Then H is a skew Hadamard matrix if and only if D ∩ D^{(−1)} = {1}.

Proof. A diagonal entry h_{ii} is −1 if and only if 1 ∈ D.

Suppose that d ≠ 1 satisfies that d, d^{−1} ∈ D. There exist indices i ≠ j and u′ ∈ N such that a_{i} ∈ N and u′a_{j} = d. Then a_{j} = (u′a_{i})a_{i}d, as a_{i}^{2} = 1, and a_{i} = (a_{i}u′)a_{j}d^{−1}. The value of h_{ij} depends on u′a_{i}, and the value of h_{ji} depends on a_{i}u′ = u′a_{i}. Thus h_{ij} = h_{ji}.

Suppose next that D ∩ D^{(−1)} = {1}. Then for g ∈ G \ N, g ∈ D if and only if g^{−1} ∉ D. For i ≠ j, h_{ij} = −1 ⇔ a_{i}^{−1}a_{j} ∈ D ⇔ a_{j}^{−1}a_{i} ∉ D ⇔ h_{ji} = 1. □

Ito [Ito94] called a group with the property of Theorem 8.4 a skew Hadamard group. From Corollary 7.3, Proposition 7.10 and Theorem 8.4 we get the following corollary.

Corollary 8.5. A group is a skew Hadamard group if and only if it is a regular subgroup of the automorphism group of D(T) for some doubly regular tournament T.

In view of Ito’s conjecture we consider the following problem.

Problem 8.6. For which values of t is the dicyclic group of order 8t a skew Hadamard group?

In what follows, we consider this problem in detail. In particular, we prove that if 4t − 1 is a prime power then the dicyclic group of order 8t is a skew Hadamard group. A computer search has shown that there are no skew Hadamard groups of order 72, see also [ItoO96].

Ito [Ito94] showed that the Hadamard matrices corresponding to Paley tournaments can be constructed from skew Hadamard groups. We state this result in terms of D(P_{q}).

Theorem 8.7. Let q ≡ 3 mod 4 be a prime power and let P_{q} be the Paley tournament of order q. Let Γ = D(P_{q}). Then SL(2, q) acts as a group of automorphisms of Γ and this group contains a dicyclic subgroup acting regularly on V (Γ).

The proof below uses the following basic property of the special linear group SL(2, q) of 2 × 2 matrices over 𝔽_{q} with determinant 1.

Lemma 8.8. SL(2, q) has order q(q − 1)(q + 1) and contains a subgroup isomorphic to the dicyclic group of order 2(q + 1).

Proof. Since SL(2, q) is isomorphic to the special unitary group SU(2, q^{2}) (see [Hup67, Hilfssatz II.8.8]), it suffices to find a subgroup of SU(2, q^{2}) isomorphic to the dicyclic group. Let λ ∈ 𝔽_{q^{2}}^{∗} be an element of order q + 1. Let

x = ( \begin{matrix}λ & 0 \\ 0 & λ^{q} \end{matrix} ) , y = ( \begin{matrix}0 & 1 \\ −1 & 0 \end{matrix} ) .

Then x, y ∈ SU(2, q^{2}), x^{\frac{q+1}{2}} = y^{2}, y^{4} = 1, xyx = y and so x and y generate a dicyclic subgroup of SU(2, q^{2}) of order 2(q + 1). □

Proof of Theorem 8.7. Let 𝔽_{q}^{∗} = 𝔽_{q} \ {0} be the multiplicative group of the finite field of order q. Let Q be the set of nonzero squares in 𝔽_{q} and let N = 𝔽_{q}^{∗} \ Q. Then Q is a subgroup of 𝔽_{q}^{∗} of index 2, and N = −Q as −1 ∉ Q. Let V = 𝔽_{q}^{2} be the 2-dimensional vector space of row vectors over 𝔽_{q}. We define a relation ∼ on V \ {0} by

v ∼ w if v = αw for some α ∈ Q.

This relation is an equivalence relation and we have a partition of V \{0} into equivalence classes. This relation partitions each 1-dimensional subspace into two classes. The class containing v = (x, y) will be denoted by [v] = [x, y]. We denote by X = (V \ {0})/∼ the set of all equivalence classes. The number of classes is |X| = \frac{q^{2}−1}{(q−1)/2} = 2(q + 1).

If v = αw for v, w ∈ V \ {0} and α ∈ Q then vA = αwA for any matrix A ∈ GL(2, q). Thus the natural action of GL(2, q) on V \ {0} by right multiplication preserves the relation ∼.

For any [α, β] ∈ X, the matrix ( \begin{matrix}α & β \\ 0 & α^{−1} \end{matrix} ), or if α = 0 the matrix ( \begin{matrix}α & β \\ −β^{−1} & 0 \end{matrix} ), has

determinant 1 and maps [1, 0] to [α, β]. It follows that the special linear group

G = SL(2, q) = {g ∈ GL(2, q) | det(g) = 1}

acts transitively on X by right multiplication. If some matrix g ∈ G fixes every [v] ∈ X then g = λI for some λ ∈ Q. Since det(g) = λ^{2} = 1 and λ ∈ Q, λ = 1. Thus G acts faithfully on X. The stabilizer of [1, 0] is

G_{[1,0]} = \{( \begin{matrix}α & 0 \\ γ & α^{−1} \end{matrix} ) | α ∈ Q, γ ∈ 𝔽_{q}\} .

The group G has an action on X × X defined by (x, y)^{g} = (xg, yg) for all x, y ∈ X and g ∈ G. Let E be the orbit in this action containing ([1, 0], [0, 1]) and let Γ be the graph with vertex set X and arc set E. We need to prove that Γ is isomorphic to D(P_{q}).

The set of out-neighbours of [1, 0] is the orbit containing [0, 1] under the action of G_{[1,0]} on X. The orbit consists of elements of the form [γ, α^{−1}] = [β, 1] (where β = αγ).

Since the matrix ( \begin{matrix}β & −1 \\ 1 − β^{2} & β \end{matrix} ) ∈ G maps ([1, 0], [β, 1]) to ([β, −1], [1, 0]) the in-

neighbours of [1, 0] are the elements [β, −1], β ∈ 𝔽_{q}.

Thus [−1, 0] is the unique vertex not adjacent to [1, 0]; the automorphism ( \begin{matrix}−1 & 0 \\ 0 & −1 \end{matrix} )

∈ G shows that [−1, 0] has in-neighbours [β, 1] and out-neighbours [β, −1].

Any automorphism g ∈ G mapping [1, 0] to [v] ∈ X also maps [−1, 0] to the unique vertex [−v] not adjacent to [v]. Since G acts transitively on arcs of Γ (by definition of E = E(Γ)), on E^{t} = {(x, y) | (y, x) ∈ E} and on pairs of nonadjacent vertices, Γ is a doubly regular (q + 1, 2)-team tournament. Since there are q paths of length 2 from [1, 0] to [−1, 0], Γ is isomorphic to D(N^{+}([1, 0])) by Theorem 4.6.

Let [α, 1], [β, 1] ∈ N^{+}([1, 0]). An element g ∈ G maps ([1, 0], [0, 1]) to ([α, 1], [β, 1]) if

and only if g = ( \begin{matrix}δα & δ \\ ϵβ & ϵ \end{matrix} ), where δ, ϵ ∈ Q. Since det(g) = (α − β)δϵ, such δ, ϵ exist if

and only α − β ∈ Q. Thus ([α, 1], [β, 1]) ∈ E(Γ) if and only α − β ∈ Q. By Lemma 3.6, N^{+}([1, 0]) is isomorphic to the Paley tournament P_{q} and so Γ is isomorphic to D(P_{q}).

It follows from Lemma 8.8 that there is a subgroup H < G = SL(2, q) isomorphic to the dicyclic group of order 2(q + 1), and that the stabilizer G_{[1,0]} in G of [1, 0] has order \frac{q(q−1)(q+1)}{2(q+1)} = \frac{1}{2}q(q − 1), as |X| = 2(q + 1). Thus the order of the stabilizer H_{[1,0]} in H of [1, 0] divides \frac{1}{2}q(q − 1). It also divides |H| = 2(q + 1). Since \frac{1}{2}q(q − 1) and 2(q + 1) are relatively prime, H_{[1,0]} = 1. Since |H| = |X|, H acts regularly on X. □

Example 8.9. Other groups than the dicyclic groups may appear as regular subgroups of the automorphism groups of graphs D(T). We show some examples found with the use the computer algebra system GAP [GAP] and its share package GRAPE [Soi93] together with nauty [McKay90].

(1) By Theorem 8.7, the automorphism group of D(P_{q}) has a regular group isomorphic to the dicyclic group of order 2q + 2. However, for some values of q there are additional regular subgroups.

The automorphism group of D(P_{11}) has two conjugacy classes of regular subgroups. One class consists of dicyclic groups of order 24. The other class consists of groups isomorphic to ⟨x, y, z | x^{2} = y^{2}, y^{4} = z^{3} = 1, xyx = y, zx = yz, zy = xyz⟩ ≃ SL(2, 3).

The automorphism group of D(P_{23}) has three conjugacy classes of regular subgroups. One class consists of dicyclic groups of order 48. The other two classes consist of groups isomorphic to ⟨x, y, z, w | x^{2} = y^{2} = w^{2}, y^{4} = z^{3} = 1, xyx = y, zx = yz, zy = xyz, wx = yw, wy = xw, wz = xz^{2}w⟩.

The automorphism group of D(P_{59}) also has three conjugacy classes of regular subgroups. One class consists of dicyclic groups of order 120. The other two classes consist of groups isomorphic to SL(2, 5).

(2) Let EP_{q} be the doubly regular tournament of order 2q + 1 obtained by applying Theorem 3.7 to the Paley tournament P_{q} for a prime power q ≡ 3 mod 4, and let G be the automorphism group of D(EP_{q}). Then it was proved in [Jør94] that G acts transitively on the vertices. Computer experiments show that for small values of q (at least up to q = 47) G has a regular subgroup isomorphic to the dicyclic group.

For q = 11 there is one additional regular subgroup, isomorphic to the group ⟨x, y, z, w | x^{2} = y^{2} = w^{2}, y^{4} = z^{3} = 1, xyx = y, zx = yz, zy = xyz, wx = yw, wy = xw, wz = xz^{2}w⟩ of order 48 appearing in part (1).

(3) There is a tournament T of order 23 such that D(T) is a Cayley graph for the group G = ⟨x, y, z | x^{6} = y^{2}, x^{3} = z^{2}, y^{4} = 1, xyx = y, zx = x^{5}z, zy = x^{3}yz⟩. This is the full group of automorphisms of D(T), i.e., T has a trivial automorphism group.

There is, in fact, a natural explanation for the exceptional groups of order 24, 48 and 120 appearing in Example 8.9(1). They are the well-known binary polyhedral groups (see [CoxM80, § 6.5], for instance), which are double coverings of the finite rotation groups of the tetrahedron (isomorphic to the alternating group A_{4}), of the cube and octahedron (isomorphic to the symmetric group S_{4}) and of the icosahedron and dodecahedron (isomorphic to A_{5}). These rotation groups are isomorphic to subgroups of the projective special linear group P SL(2, q) = SL(2, q)/{±I} for certain prime powers q (see [Hup67, Hauptsatz II.8.27] for details), and the corresponding binary groups are their inverse images in SL(2, q). As subgroups of SL(2, q), these binary groups act semiregularly on the 2(q + 1) vertices of D(P_{q}) since they have trivial intersections with the vertex-stabilisers in SL(2, q). When q = 11, 23 or 59 respectively they have order 2(q + 1) and therefore act regularly. Moreover, it follows from Dickson’s description of the subgroups of P SL(2, q) [Hup67, Hauptsatz II.8.27] that these are the only examples of non-dicyclic regular subgroups of SL(2, q). In a similar way, the dicyclic regular subgroups in Theorem 8.7 and Example 8.9(1) are the double covers in SL(2, q) of dihedral rotation groups of order q +1 in P SL(2, q); these arise for all prime powers q ≡ 3 mod 4.

9. Concluding remarks

In this section we wish to discuss a number of issues which do not belong properly to the main part of the text. However we hope that they will clarify some historical and presentational aspects, and will help better to define the genre of the paper, putting it in context within the wider scope of Algebraic Graph Theory.

9.1 This project belongs to the area of Algebraic Graph Theory (which we abbreviate to AGT). This name was coined about 40 years ago by Norman Biggs; initially there was also a tendency to use the alternative name Algebraic Combinatorics (as suggested in [BanI84]), though nowadays this latter name is used in a much wider context.

Loosely speaking, AGT deals with diverse techniques which allow one to investigate all possible aspects of symmetry of graphs, distinguishing group-theoretic, spectral, numbertheoretic and purely combinatorial features of the concept of symmetry. In our eyes, the recent book [BroH12] vividly, though concisely, reflects almost all the significant facets of AGT.

9.2 This project began in 1994, when the author MK visited SYS at Ames. We started with a 12-page handwritten draft, prepared by SYS after discussion of a few examples of class 3 association schemes and their links with S-rings. A year later this was transformed into a first printed text with a brief outline of further steps which needed to be completed.

Another source, at that time independent, was a one-page handwritten text prepared by GJ, who realised that some of the isolated examples provided by MK and SYS could be generalised to an infinite series with the aid of the groups SL(2, q). This happened in 1997 at Beer Sheva, where a few days later the draft was extended to a 4-page dense text, in which the concept of doubly regular orientation was considered.

In 2000 LJ, visiting Beer Sheva, drew MK’s attention to his preprint [Jør94b] with its agenda around the newly introduced concept of a normally regular digraph, various constructions of such graphs and their links with Cayley graphs, difference sets and doubly regular tournaments. LJ’s familiarity with these topics, as well as a few new examples discovered by him with the aid of a computer, stimulated the authors to combine their efforts. In 2001, during a visit of MK to Aalborg, a first draft of the existing text (at that time 17 pages) was prepared and distributed between the authors. Nevertheless it took another two years before MK and LJ added six more pages to the text, when they met at Newark, DE.

In 2005, at Southampton, the current structure of the text was formed, and in 2008 it reached its existing state. Unfortunately, due to a lack of efficient communication and, probably, adequate leadership, it took us other six years to realise that the project was, in principle, finished and should be published as soon as possible. Here we remind the reader of the saying “better late than never”.

9.3 Needless to say, during this 20-year period the entire mathematical community was not dreaming, patiently awaiting our contribution. This is why nowadays the available literature contains many intersections with our approach and results, some of them briefly discussed below. However we believe that it still makes sense to publish our text as it is. It seems that the traditions of the journal SLC do not contradict this vision.

9.4 The style of this paper is a mixture of several relevant genres: research report, survey of ideas and examples, short review of the literature and also elements of an essay. An essential feature of the chosen approach is that it is in a sense genetic. Step by step we have introduced necessary background, new definitions, helpful examples, and proofs of results, while the discussion of some links with the existing literature has intentionally been postponed to the very end of this final section or even neglected.

To give just one example, we think that the spectral theorem for normal matrices is a classical result, but it would be difficult to attribute it fairly to one specific reference. Fortunately, in the era of Wikipedia a single click on the internet allows one to reach a wide range of relevant information.

9.5 Below is a brief summary of the material presented here, intentionally expressed in a slightly different wording in comparison with the preceding main part of the text.

We have investigated combinatorial structures obtained by relaxing the conditions on a non-symmetric three-class association scheme and in particular the conditions for an imprimitive three-class association scheme. In many cases there are relations with certain types of Hadamard matrices.

For doubly regular team tournaments we have seen that all known examples are relations of an imprimitive three-class association scheme, and that examples that are not association schemes can exist only for one particular family of parameters (Type III). Similarly in [Jør14] it is proved that a group divisible normally regular digraph (i.e. an orientation of a complete multipartite graph) has either four or five distinct eigenvalues, and if it has four eigenvalues then it is a relation of a three-class association scheme. It is not known whether there exist any group divisible normally regular digraphs with five eigenvalues.

In the primitive case the situation is quite different. Only one infinite family and a few exceptional examples of primitive non-symmetric three-class association schemes are known (see [Jør10]). However, several families of normally regular digraphs are known, see [Jør94b] or [Jør14]. We have not investigated general digraphs satisfying the equation of Definition 3.13.

9.6 Association schemes form one of the background concepts in this paper. A classical book [BanI84] still serves as an introduction to this part of algebraic combinatorics. The main line of the presentation in [BanI84] deals with P - and Q-polynomial association schemes, and also with related distance regular graphs. Schemes with few classes are related to another possible view of this area. In particular, symmetric schemes with two classes are well known in the equivalent form of pairs of complementary strongly regular graphs, while non-symmetric schemes with two classes are associated in the same way with doubly regular tournaments.

Surprisingly, the next case of schemes with three classes has received less attention in the literature. Significant sources for the study of symmetric 3-class schemes are the thesis [Cha94] and [vDam99].

Our paper is strictly related to the case of non-symmetric association schemes with three classes. The most significant text here is the unpublished report [GolC93]. Only small extracts and extensions of it have been published, see [GolC96a], [GolC96] and [GolC98]. An interesting precursor of this approach (in purely permutation group theoretic language) is [Iwa73]. Both texts by SYS, [So95] and [So96], were prepared without any previous knowledge of or access to [GolC93]. Our acquaintance with this source goes back to a time when most of the current text had already been written. This is one of the main reasons for the chosen genetic style of presentation.

The paper [Ma07] discusses some families of association schemes on 4^{k} vertices in relation to Galois rings of characteristic 4. Non-symmetric commutative schemes with few classes are also investigated in [ChiaK06]. We also mention the paper [Jør09] by LJ.

9.7 Relative difference sets form a significant source of inspiration, which influenced research in related areas over a long period. This concept was introduced by J.E.M. Elliot and A.T. Butson [EllB66] and was the subject of investigations in design theory, which are of their own independent interest. A generalisation of this concept together with a number of resulting combinatorial objects was suggested in [AraJP90]. In [DavP10] various kinds of difference sets are exploited for the construction of non-symmetric association schemes with three classes. We also mention a few other applications of relative difference sets: extremal graphs of girth 5 in [Jør05], antipodal distance regular Cayley graphs in [CheL05], and nonlinear functions for cryptographic purposes in [Hor10].

9.8 Noboru Ito, who in a sequence of papers coined the concept of a Hadamard group, started to use such groups in design theory and initiated a hope that their use might provide “a golden way” towards a proof of the Hadamard conjecture. Ito’s ideas have been successfully developed in several directions. Here we mention just [AraCP01], where Hadamard groups are used in conjunction with relative difference sets, and also [KimN02], devoted to Hadamard matrices of dihedral group type.

In a more sophisticated way, group-theoretic constructions are used in [IonK03], supporting diverse links between designs and doubly regular tournaments (digraphs).

We also mention a recent paper [NozS12], where doubly regular tournaments and normal matrices are considered together with the concept of an almost regular tournament.

9.9 In this paper, we have studied groups of automorphisms of various combinatorial structures, which act transitively, and in many cases regularly, on the points. The full automorphism groups of these structures are also of interest: for instance, one can show that the automorphism group of the digraph D(P_{q}) is ΣL(2, q), an extension of the group SL(2, q) in Theorem 8.7 by the Galois group of the field 𝔽_{q} (a cyclic group of order e where q = p^{e} for some prime p). However, not wishing to add to the already unusual gestation period of this paper (see Section 9.2), we have left a closer investigation of these groups to a later date.

10. Acknowledgements

This project, at different stages of its development, was supported by the Departments of Mathematics at Ben-Gurion University, Iowa State University and the University of Southampton, as well as the Department of Mathematical Sciences at Aalborg University. It has also been supported by the project: Mobility — enhancing research, science and education at the Matej Bel University, ITMS code: 26110230082, under the Operational Program Education cofinanced by the European Social Fund. In addition, LJ and MK are pleased to acknowledge the support of the Department of Mathematical Sciences at the University of Delaware. We are very grateful to two anonymous referees for many helpful comments, which were used in preparing the final version of this paper.

References

[AraCP01] K. T. Arasu, Y. Q. Chen and A. Pott, Hadamard and conference matrices, J. Algebraic Combin. 14 (2001), 103–117.

[AraJP90] K. T. Arasu, D. Jungnickel and A. Pott, Divisible difference sets with multiplier −1, J. Algebra 133 (1990), 35–62.

[BanI84] E. Bannai and T. Ito, Algebraic combinatorics. I. Association schemes. The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA (1984).

[BethJL85] T. Beth, D. Jungnickel and H. Lenz, Design theory. Bibliographisches Institut (1985).

[BroH12] A. E. Brouwer and W. H. Haemers, Spectra of graphs. Universitext, Springer (2012).

[Cha94] Y. Chang, Imprimitive symmetric rank 4 association schemes. Ph.D. thesis, University of Michigan (1994), 82 pp, ProQuest LLC.

[CheL05] Y. Q. Chen and C. H. Li, Relative difference sets fixed by inversion and Cayley graphs, J. Combin. Theory Ser. A 111 (2005), 165–173.

[ChiaK06] G. L. Chia and W. K. Kok, On non-symmetric commutative association schemes with exactly one pair of non-symmetric relations, Discr. Math. 306 (2006), 3189–3222.

[CoxM80] H. S. M. Coxeter and W. O. J. Moser, Generators and Relations for Discrete Groups, 4th ed., Springer-Verlag, Berlin – Heidelberg – New York (1980).

[DavP10] J. A. Davis and J. Polhill, Difference set constructions of DRADs and association schemes, J. Combin. Theory Ser. A 117 (2010), 598–605.

[DinWX07] C. Ding, Z. Wang and Q. Xiang, Skew Hadamard difference sets from the Ree–Tits slice symplectic spreads in PG(3, 3^{2h+1}), J. Combin. Theory, Ser. A 114 (2007), 867–887.

[DinY06] C. Ding and J. Yuan, A family of skew Hadamard difference sets, J. Combin. Theory, Ser. A 113 (2006), 1526–1536.

[EllB66] J. E. H. Elliot and A. T. Butson, Relative difference sets, Illinois J. Math. 10 (1966) 517–531.

[GAP] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.1 , Aachen, St An-

    drews (1999), (http://www-gap.dcs.st-and.ac.uk/~gap).

[GolC93] R. W. Goldbach and H. L. Claasen, On symmetric 3-class association schemes, Report 93-125. Delft Univ. of Tech., Delft (1993).

[GolC96] R. W. Goldbach and H. L. Claasen, The structure of imprimitive non-symmetric 3-class association schemes, Europ. J. Combin. 17 (1996), 23–37.

[GolC96a] R. W. Goldbach and H. L. Claasen, Feasibility conditions for non-symmetric 3-class association schemes, Discr. Math. 159 (1996), 111–118.

[GolC98] R. W. Goldbach and H. L. Claasen, 3-class association schemes and Hadamard matrices of a certain block form, Europ. J. Combin. 19 (1998), 943–951.

[Gor68] D. Gorenstein, Finite Groups, Harper and Row, New York (1968).

[Hig75] D. G. Higman, Coherent configurations. I. Ordinary representation theory. Geometriae Dedicata 4 (1975), 1–32.

[Hor10] K. J. Horadam, Relative difference sets, graphs and inequivalence of functions between groups, J. Combin. Des. 18 (2010), 260–273.

[Hup67] B. Huppert, Endliche Gruppen I, Springer-Verlag, Berlin (1967).

[IonK03] Y. Ionin and H. Kharaghani, Doubly regular digraphs and symmetric designs, J. Combin. Theory Ser. A 101 (2003), 35–48.

[Ito94] N. Ito, On Hadamard groups. J. Algebra 168 (1994), 981–987.

[Ito97] N. Ito, On Hadamard groups. III. Kyushu J. Math. 51 (1997), 369–379.

[ItoO96] N. Ito and T. Okamoto, On Hadamard groups of order 72, Algebra Colloq. 3 (1996), 307–324.

[Iwa73] S. Iwasaki, On finite permutation groups of rank 4, J. Math. Kyoto Univ. 13 (1973), 1–20. [Jør94] L. K. Jørgensen, Isomorphic switching in tournaments, Congressus Numerantium 104 (1994),

217–222. [Jør94b] L. K. Jørgensen, On normally regular digraphs, Report R 94-2023, Department of Mathematics

and Computer Science, Aalborg University (1994). [Jør05] L. K. Jørgensen, Girth 5 graphs from relative difference sets, Discrete Math. 293 (2005), 177–184. [Jør09] L. K. Jørgensen, Algorithmic approach to non-symmetric 3-class association schemes, Algorithmic

algebraic combinatorics and Gröbner bases, pp. 251–268, Springer (2009). [Jør10] L. K. Jørgensen, Schur rings and non-symmetric association schemes on 64 vertices, Discrete

Mathematics 310 (2010), 3259–3266. [Jør14] L. K. Jørgensen, Normally regular digraphs, arXiv:1410.8424v1, 30 Oct. 2014.

[KimN02] H. Kimura and T. Niwasaki, Some properties of Hadamard matrices coming from dihedral groups, Graphs Combin. 18 (2002), 319–327.

[Ma07] J. Ma, Three-class association schemes on Galois rings in characteristic 4, Graphs Combin. 23 (2007), 73–86.

[McKay90] B. D. McKay, nauty user’s guide (version 1.5), Technical report TR-CS-90-02, Australian National University, Computer Science Department, ANU, 1990.

[Muz10] M. Muzychuk, On skew Hadamard difference sets, arXiv:1012.2089v1, 9 Dec. 2010.

[NozS12] H. Nozaki and S. Suda, A characterization of skew Hadamard matrices and doubly regular tournaments, Linear Algebra Appl. 437 (2012), 1050–1056.

[Pal33] R. E. A. C. Paley, On orthogonal matrices, J. Mathematics and Physics 12 (1933), 311–320.

[Pas92] D. Pasechnik, Skew-symmetric association schemes with two classes and strongly regular graphs of type L_{2n−1}(4n − 1). Interactions between algebra and combinatorics. Acta Appl. Math. 29 (1992), 129–138.

[ReiB72] K. B. Reid and E. Brown, Doubly regular tournaments are equivalent to skew Hadamard matrices. J. Combin. Theory, Ser. A 12 (1972), 332–338.

[Sch99] B. Schmidt, Williamson matrices and a conjecture of Ito’s, Des. Codes Cryptogr. 17 (1999), 61–68.

[So95] S. Y. Song, Class 3 Association schemes whose symmetrizations have two classes, J. Combin. Theory, Ser. A 70 (1995), 1–29.

[So96] S. Y. Song, Commutative association schemes whose symmetrizations have two classes, J. Algebraic Combin. 5 (1996), 47–55.

[Soi93] L. H. Soicher, GRAPE: a system for computing with graphs and groups. In: Groups and Computation (eds.: Finkelstein and Kantor), vol. 11 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 287–291. American Mathematical Society (1993).

[Sze69] G. Szekeres, Tournaments and Hadamard matrices, Enseignement Math. 15 (1969), 269–278.

[vDam99] E. van Dam, Three-class association schemes. J. Algebraic Combin. 10 (1999), 69–107.