Perfect factorisations of bipartite graphs and Latin squares without proper subrectangles

I. M. Wanless

Department of Mathematics and Statistics University of Melbourne Parkville Vic 3052 Australia

ianw@ms.unimelb.edu.au

Submitted: November 16, 1998; Accepted January 22, 1999. AMS Classifications: 05B15, 05C70.

A Latin square is pan-Hamiltonian if every pair of rows forms a single cycle. Such squares are related to perfect 1-factorisations of the complete bipartite graph. A square is atomic if every conjugate is pan-Hamiltonian. These squares are indivisible in a strong sense – they have no proper subrectangles. We give some existence results and a catalogue for small orders. In the process we identify all the perfect 1-factorisations of K_{n,n} for n ≤ 9, and count the Latin squares of order 9 without proper subsquares.

§1. Introduction

For k ≤ n, a k × n Latin rectangle is a k × n matrix of entries chosen from some set of symbols of cardinality n, such that no symbol is duplicated within any row or any column. Typically we assume that the symbol set is {1, 2, …, n}. We use L(k, n) for the set of k × n Latin rectangles. Elements of L(n, n) are called Latin squares of order n. The symbol in row r, column c of a Latin rectangle R is denoted by R_{rc}. A Latin square S is idempotent if S_{ii} = i for each i.

If the symbol set of a Latin rectangle R is {1, 2, …, n} then each row r is the image of some permutation σ_{r} of that set. That is, R_{ri} = σ_{r}(i). Moreover, each pair of rows (r, s) defines a permutation by σ_{r,s} = σ_{r}σ_{s}^{−1}. Naturally σ_{r,s} = σ_{s,r}^{−1}. Any of these permutations may be written as a product of disjoint cycles in the standard way. If this product consists of a single factor we call the permutation a full cycle permutation.

A subrectangle of a Latin rectangle is a submatrix (not necessarily consisting of adjacent entries) which is itself a Latin rectangle. If it happens to be a Latin square it is called a subsquare. An a × b subrectangle of a k × n Latin rectangle is proper provided we have the strict inequalities 1 < a < k and 1 < b < n. A Latin square without subsquares of order 2 is said to be N_{2} and a Latin square without proper subsquares is N_{∞}. Latin squares with no proper subrectangles will be of central interest in this paper.

There are some important equivalence relations for Latin squares. Two squares are isotopic if one can be obtained from the other by rearranging the rows, rearranging the columns and renaming the symbols. The set of all squares isotopic to a given square forms an isotopy class. The second operation is conjugacy. Here instead of permuting within the sets of rows, columns and symbols, we permute the sets themselves. For example, starting with a square S, we might interchange rows with columns to get S^{T}, the transpose of S. Alternatively, we could interchange the roles of columns and symbols to get a square R^{−1}(S), which we call the row inverse of S. Note that R^{−1}(S) can be obtained from S by replacing σ_{r} by σ_{r}^{−1} in each row r. If it happens that S = R^{−1}(S) then clearly each σ_{r} must be an involution and we say that S is involutory. The operations of transposition and row inverse generate a conjugacy class consisting of 6 conjugates {S, S^{T} , R^{−1}(S), (R^{−1}(S))^{T} , R^{−1}(S^{T}), (R^{−1}(S^{T}))^{T} }. The closure of an isotopy class under conjugacy yields a main class.

Two edges of a graph are independent if they do not share a common vertex. A set of pairwise independent edges which covers the vertices of a graph is called a 1-factor (also known as a perfect matching). A partitioning of the edges of a graph into 1-factors is a 1-factorisation. A 1-factorisation is perfect if the union of any two of its 1-factors is a single (Hamiltonian) cycle. For a full discussion of 1-factorisations see [14], and for a short summary of known results consult [1].

There is a close relationship between Latin rectangles and 1-factorisations in regular bipartite graphs, in which each row of a rectangle corresponds to a 1-factor. For each R ∈ L(k, n) we can form G(R), a k-regular subgraph of K_{n,n} in which the vertex sets correspond to the columns and the symbols, and an edge indicates that the symbol is used in the column. The Latin property of R means that the edges corresponding to the (column, symbol) pairs within a row are a 1-factor, and the 1-factors corresponding to different rows are disjoint. Hence R prescribes a 1-factorisation of G(R) in a natural way. In this paper we investigate the case where the 1-factorisation happens to be perfect. An alternative way to view our results in terms of transversal designs will be discussed briefly in §5.

If R is a 2×a subrectangle of some Latin square L, and R is minimal in that it contains no 2×b subrectangle for b < a, then we say that R is a row cycle of length a. Column cycles and symbol cycles are defined similarly, and the operations of conjugacy on L interchange these objects. Note that there is a natural 1:1 length-preserving correspondence between row cycles involving rows r, s and cycles in σ_{r,s}. We are interested in the case where all row cycles are as long as possible:

Definition. A Latin rectangle R ∈ L(k, n) is pan-Hamiltonian if every row cycle of R has length n. Equivalently, R is pan-Hamiltonian if σ_{r,s} is a full cycle permutation for each pair of rows r, s in R.

The name pan-Hamiltonian comes from [9], where it is used to describe a Latin square in which each symbol cycle is Hamiltonian. We prefer to base our definition on row cycles because it then makes sense for Latin rectangles which are not squares. Our definition is clearly related to that of [9] by conjugacy.

§2. Basic properties

We examine a few simple properties of pan-Hamiltonian squares. Firstly, from the discussion in the introduction we have:

Lemma 1. There is a pan-Hamiltonian square of order n if and only if K_{n,n} has a perfect 1-factorisation.

In fact the concepts of pan-Hamiltonian squares and bipartite perfect 1-factorisations are so closely linked that in what follows we will sometimes consider them synonymous. Our second result provides further motivation for our study.

Lemma 2. A Latin square is pan-Hamiltonian if and only if it contains no proper subrectangles. In particular every pan-Hamiltonian square is N_{∞}.

Proof: If L ∈ L(n, n) is not pan-Hamiltonian then it contains a row cycle of length less than n and this row cycle immediately gives a proper subrectangle. Conversely, suppose L contains a proper subrectangle R. Then R has at least two rows so it contains at least one row cycle C. For R to be proper, C must have length less than n. But C is a row cycle of L, so L is not pan-Hamiltonian. ⊙

Lemma 2 gives a good reason to be interested in pan-Hamiltonian Latin squares, but also shows that constructing them is likely to be difficult. Note that at this stage the existence question for N_{∞} squares is not completely resolved. Heinrich [8] gave a construction for n = pq ≠ 6 where p and q are prime, which was later generalised in [2] to all orders except those of the form 2^{a}3^{b}. Only a few sporadic orders from the remaining case have since been settled. Some small order examples have been discovered by computer searches. Perfect 1-factorisations have also been successfully employed and offer greater hope of producing infinite classes of examples.

Lemma 3. If L is a pan-Hamiltonian square then so is any square isotopic to L, and so is R^{−1}(L).

Proof: Isotopies preserve the lengths of row cycles and hence also the pan-Hamiltonian property. The implication that R^{−1}(L) is pan-Hamiltonian follows from the observation that the inverse of a full cycle permutation is also a full cycle permutation. ⊙

Note that the operations discussed in Lemma 3 correspond to the natural notion of isomorphism for perfect 1-factorisations. Suppose that from a Latin square L we construct a complete bipartite graph G with vertex sets U and V, and a 1-factorisation of G with 1-factors F. Then an isotopy of L corresponds to a relabelling/reordering of the sets U, V and F. Also, taking the row inverse of L corresponds to switching the sets U and V. For a formal definition of isomorphism between 1-factorisations, and some invariants with which to distinguish non-isomorphic factorisations, see Chapter 11 of [14]. One of the ideas there is that of a train, which we now define for factorisations of complete bipartite graphs.

Suppose we have G, a copy of K_{n,n} in which the vertex sets are U and V. We define T (F), the train of a 1-factorisation F of G, to be a directed graph (with loops) on the triples in U ×V ×F. Each of the n^{2}(n−1) vertices has outdegree 1. The edge from [u, v, f] goes to [u′, v′, f′] where f contains the edges uv′ and u′v and f′ contains the edge uv. It should be clear that two isomorphic factorisations of G must have isomorphic trains.

It is worth pointing out that although the factorisations corresponding to L and R^{−1}(L) are isomorphic, the squares L and R^{−1}(L) may or may not be isotopic. Examples of both types will be given in §6.

A particularly simple Latin square on the set {1, 2, …, n} is the Cayley table C_{n} of the cyclic group of order n. Here C = C_{n} is defined by C_{ij} ≡ i + j − 1 (mod n). By symmetry all row cycles in C_{n} have length dividing n. If n happens to be prime the row cycles must be of length n, so C_{n} will be a pan-Hamiltonian Latin square. Hence

Lemma 4. Perfect 1-factorisations of K_{p,p} exist for all prime p.

In the next section we strengthen Lemma 4, by constructing non-isomorphic perfect 1-factorisations of K_{p,p} from a perfect 1-factorisation of K_{p+1}.

For any Latin square L, define ν(L) to be the number of conjugates of L which are pan-Hamiltonian. Note that ν(·) is a main class invariant as a consequence of Lemma 3, so we can sensibly write ν(M) for a main class M. An interesting property of C_{n} is that it is isotopic to all of its conjugates (Theorem 4.2.2 of [5]). So by Lemma 3, ν(C_{p}) = 6 for prime p. In other words, every square in the main class of C_{p} is pan-Hamiltonian. In general this is not true of main classes containing pan-Hamiltonian squares. As we shall see in §6 below, all Latin squares L of order at most 9 (other than those isotopic to C_{p} for some prime p) have ν(L) either 0 or 2. Note that ν(L) ∈ {0, 2, 4, 6} by Lemma 3. All of these values are achievable. In §4 we will look at squares for which ν(·) = 6. To find a square for which ν(·) = 4 it is useful to consider possible symmetries of the square:

Lemma 5. Suppose L is a pan-Hamiltonian square. If L is isotopic to R^{−1}(L) then ν(L) ∈ {2, 6}. Alternatively, if L is isotopic to L^{T} then ν(L) ∈ {4, 6}. Proof: We write A ∼ B if both A and B are pan-Hamiltonian, or neither is. Let the conjugates of L be L_{1} = L, L_{2} = L^{T}, L_{3} = R^{−1}(L), L_{4} = (R^{−1}(L))^{T}, L_{5} = R^{−1}(L^{T}), L_{6} = (R^{−1}(L^{T}))^{T}. Note that L_{1} is pan-Hamiltonian by assumption. We make use of Lemma 3, starting with the observation that L_{1} ∼ L_{3}, L_{2} ∼ L_{5} and L_{4} ∼ L_{6}. If L_{1} and L_{3} are isotopic then L_{2} ∼ L_{4} and L_{5} ∼ L_{6} because they are also isotopic pairs. But then L_{2} ∼ L_{4} ∼ L_{5} ∼ L_{6}, from which the first assertion of the lemma follows. A similar argument works if L_{1} ∼ L_{2}. In this case L_{3} ∼ L_{5} and L_{4} ∼ L_{6}, so that L_{1} ∼ L_{2} ∼ L_{3} ∼ L_{5} and at least four conjugates are pan-Hamiltonian. ⊙

As an application of Lemma 5, we will meet pan-Hamiltonian squares in the next section which are derived from perfect 1-factorisations of complete graphs. These squares are involutory, so they always have ν(·) ∈ {2, 6}. The other part of Lemma 5 is more promising for finding examples of squares for which ν(·) = 4. Indeed such a square is given in (1). This square is symmetric about its main diagonal so it is sufficient to note that it is pan-Hamiltonian but that the symbols 1 and 11 form three separate symbol cycles.

( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 1 \\ 3 & 4 & 5 & 6 & 11 & 8 & 1 & 10 & 7 & 9 & 2 \\ 4 & 5 & 6 & 7 & 9 & 2 & 11 & 1 & 8 & 3 & 10 \\ 5 & 6 & 11 & 9 & 4 & 1 & 10 & 7 & 3 & 2 & 8 \\ 6 & 7 & 8 & 2 & 1 & 10 & 3 & 11 & 5 & 4 & 9 \\ 7 & 8 & 1 & 11 & 10 & 3 & 9 & 4 & 2 & 6 & 5 \\ 8 & 9 & 10 & 1 & 7 & 11 & 4 & 2 & 6 & 5 & 3 \\ 9 & 10 & 7 & 8 & 3 & 5 & 2 & 6 & 11 & 1 & 4 \\ 10 & 11 & 9 & 3 & 2 & 4 & 6 & 5 & 1 & 8 & 7 \\ 11 & 1 & 2 & 10 & 8 & 9 & 5 & 3 & 4 & 7 & 6 \end{matrix} )  (1)

In Lemma 4 we saw an existence result for pan-Hamiltonian Latin squares of some orders. Now we look at some orders for which these squares do not exist.

Lemma 6. If R ∈ L(k, n) is pan-Hamiltonian then either n is odd or k ≤ 2. Proof: Suppose n is even and that r, s are two rows of R. By definition, σ_{r,s} is a full cycle permutation on an even number of symbols. In particular σ_{r,s} is an odd permutation, so σ_{r} and σ_{s} must be of different parities. As this is true for any pair of rows in R, we see that there cannot be more than 2 rows. ⊙ Corollary. Up to isomorphism, C_{2} is the only pan-Hamiltonian Latin square of even order.

Gibbons and Mendelsohn [7] attempted to find a pan-Hamiltonian square of order 12, because they knew such a square would be N_{∞} (see Lemma 2). Lemma 6 explains why their search failed, and also rules out using pan-Hamiltonian squares to completely settle the remaining existence questions for N_{∞} squares. The best we can hope for is to find examples for the orders which are powers of three. This has been achieved [6] for sporadic orders including 3^{a} for a ≤ 5, by the techniques discussed in the next section.

§3. Factorisations of complete graphs

In this section we examine connections between perfect 1-factorisations of complete graphs and those in complete bipartite graphs.

In [6, pg116] a construction is provided for an N_{∞} square of order n, given a perfect 1-factorisation of the complete graph K_{n+1} (which can only be found if n is odd). This construction, also given in [14] and mentioned in [2], is attributed to “A. Rosa and others”. The construction we give is related by conjugacy.

Suppose we have a factorisation F of K_{n+1} consisting of 1-factors F_{1}, F_{2}, …, F_{n}. Let the vertices of the K_{n+1} be v_{1}, v_{2}, …, v_{n+1} and rename the 1-factors if necessary so that F_{i} contains the edge v_{i}v_{n+1}. We construct a Latin square S(F) in which row i is determined from F_{i} as follows. The row permutation σ_{i} is the product of \frac{1}{2}(n − 1) disjoint 2-cycles, where there is a 2-cycle (ab) corresponding to each edge v_{a}v_{b} ∈ F_{i} \ {v_{i}v_{n+1}}. Since the factors {F_{i}} are pairwise disjoint by definition, S(F) is a Latin square. Also, by construction S(F) is involutory and idempotent. Finally, note that the row cycles involving rows i and j of S(F) correspond in a natural way to cycles in F_{i} ∪ F_{j}. In particular if F happens to be a perfect 1-factorisation then S(F) is pan-Hamiltonian. We have:

Lemma 7. The map F → S(F) is a bijection between 1-factorisations of K_{n+1} (with fixed vertex labels v_{1}, v_{2}, …, v_{n+1}) and idempotent involutory squares in L(n, n). It maps perfect 1-factorisations to pan-Hamiltonian squares.

Proof: It suffices to show the construction of S(F) is ‘reversible’. So suppose that L is an idempotent involutory square of order n. Then in L, each row permutation σ_{i} is an involution. Since L is idempotent each σ_{i} fixes i and it follows that σ_{i} cannot fix any j ≠ i without breaching the Latin property of L. Hence each σ_{i} must be a product of \frac{1}{2}(n − 1) disjoint 2-cycles. It is a simple matter now to construct the factorisation of K_{n+1} for which L is the image, by using edges corresponding to these 2-cycles. ⊙ Corollary. If K_{n+1} has a perfect 1-factorisation, then so does K_{n,n}.

The converse of this last result is not true. Note that K_{3} does not even have a 1-factor. However K_{2,2} has a perfect 1-factorisation (cf. the corollary to Lemma 6). It may well be that this (somewhat trivial) case is the only exception. This would follow, if the following widely believed conjecture were proved.

Conjecture. K_{n} has a perfect 1-factorisation for all even positive integers n.

If there is a counterexample, then by [14, p.127] it has n > 50. Note that Wallis chooses to exclude the trivial case n = 2. However we see no reason to do this given that the edge in K_{2} is a 1-factorisation and (vacuously) any two 1-factors in this factorisation form a Hamiltonian cycle.

Given the preceding comments, plus the Corollary to Lemma 7, it seems reasonable to suggest that:

Conjecture. K_{n,n} has a perfect 1-factorisation for n = 2 and all odd positive integers n.

Again, any counterexample must have n > 50. We look next at some of the constructions which justify this claim.

Suppose n is odd. We define a 1-factorisation E_{n+1} of K_{n+1}. There is one special vertex labelled ∞, the other vertices are labelled with the congruence classes of integers modulo n. For i = 1, 2, …, n, define factor f_{i} to consist of the edges (i − 1)(i + 1), (i−2)(i+2), …, (i−⌊\frac{1}{2}n⌋)(i+⌊\frac{1}{2}n⌋) together with i∞. Whenever n is prime the resulting 1-factorisation E_{n+1} is perfect [14]. Hence by employing the corollary to Lemma 7 we have an alternate proof of Lemma 4. In fact we can squeeze out a stronger result.

Lemma 8. Non-isomorphic perfect 1-factorisations of K_{p,p} exist for all prime p ≥ 7.

Proof: The construction which is the basis for Lemma 7 is not robust in the following sense. Given two isomorphic perfect 1-factorisations F_{1} and F_{2} of K_{n+1} it is possible that the perfect 1-factorisations of K_{n,n} given by S(F_{1}) and S(F_{2}) will not be isomorphic. This is the case only because of the special role played by the vertex labelled v_{n+1} in the map F → S(F). In E_{n+1} there are (up to symmetry) just two choices for v_{n+1}: either v_{n+1} = ∞ or without loss of generality v_{n+1} = 1. To prove the lemma we show that these two choices give non-isomorphic results. To do this it is sufficient to show that they produce non-isomorphic trains, as defined in §2. For the remainder of this proof all calculations will be performed modulo n.

In the first instance let v_{i} = i for i = 1, …, n and put v_{n+1} = ∞. It is easy to see that the resulting pan-Hamiltonian square S is defined by S_{ij} ≡ 2i − j, and hence is isotopic to C_{n}. Let h = 2^{−1} ≡ \frac{1}{2}(n + 1). For any vertex [u, v, f] of T (S) there is an edge to [u, v, f] from [hu − hv + f, −hu + hv + f, h^{2}u + h^{2}v + hf]. It follows that T (S) is 1-regular, since we know every vertex has outdegree 1.

Now suppose that we had swapped the labels on v_{n+1} and v_{1} before calculating a pan-Hamiltonian square S′. The definition of S′ is easy enough:

S′_{ij} ≡ \{ \begin{matrix}i & if i = j, \\ 1 & if i ≡ 2j − 1, \\ \frac{1}{2}(i + 1 + (i − 1)n) & if j = 1, \\ i − j + 1 & otherwise. \end{matrix}  (2)

We claim that in T (S′) the vertex [2, 3, 1] has indegree at least 2, assuming n ≥ 7. In fact the edges from both [n, 2, 2] and [\frac{1}{2}(n + 1), \frac{1}{2}(n + 3), \frac{1}{2}(n + 5)] terminate at [2, 3, 1] in this case. Hence the trains T (S) and T (S′) cannot be isomorphic, and we have two essentially different squares as claimed. ⊙

Apart from E_{p+1} for prime p, there is only one infinite family of perfect 1-factorisations of complete graphs known. For prime p the idea is to consider K_{2p} as the union of two graphs: K_{p,p} and a double copy of K_{p}. A 1-factorisation is then built up from 1factorisations of the two parts. For exact details the interested reader should consult [1] or [14]. We mention the result for two reasons. Firstly, the method demonstrates further connections between perfect 1-factorisations of complete bipartite graphs and complete graphs. Secondly of course, it gives the following existence result, via the corollary to Lemma 7.

Lemma 9. If p is prime then K_{2p−1,2p−1} has a perfect 1-factorisation.

In this section we have looked for perfect 1-factorisations of K_{n,n} which are derived from perfect 1-factorisations of K_{n+1}. As a footnote we observe that in general there are plenty of perfect 1-factorisations of K_{n,n} which do not correspond in any obvious way to a perfect 1-factorisation of K_{n+1}. We shall see in §6 that up to isomorphism there are 37 perfect 1-factorisations of K_{9,9} and only one of K_{10}.

§4. Atomic squares

In his review [13] of [8], Stein discusses Latin squares with an indivisibility property stronger than N_{∞}. In our language, Stein’s squares are those S for which neither S nor S^{T} has a proper subrectangle. Perhaps a more natural concept is obtained by not favouring rows and columns over symbols. Hence, Definition. A Latin square is atomic if none of its conjugates has a proper subrectangle.

The example (1) confirms that the atomic squares are a strict subset of Stein’s squares. Of course we use the name ‘atomic’ here in the classical sense, meaning ‘indivisible’. We have the following characterisation.

Lemma 10. A Latin square L is atomic if and only if ν(L) = 6. To test whether L is atomic it suffices to establish that L, L^{T} and (R^{−1}(L))^{T} are pan-Hamiltonian.

Proof: By Lemma 3 the three listed conjugates are pan-Hamiltonian if and only if all six conjugates of L are pan-Hamiltonian. The remainder of the lemma is a straightforward application of Lemma 2. ⊙

Stein’s main question in [13] is one of existence. We are now in a position to partly answer his query. Firstly, when p is prime we know by Lemma 10 that C_{p} is atomic since ν(C_{p}) = 6. This much was alluded to by Stein [13]. However, by combining Lemma 10 with Lemma 6 we also know that atomic squares of even composite order do not exist.

So far the only examples of atomic squares we have seen are the family of C_{p} for p prime. To show that the class is broader, we now display a second infinite(?) family, although this family also consists only of prime orders.

Lemma 11. Let p ≥ 11 be a prime. If 2 is a primitive root modulo p then there exists an atomic square of order p outside the main class of C_{p}.

Proof: We show that the non-isomorphic 1-factorisations exhibited in Lemma 8 both lead to atomic squares. The first of these 1-factorisations gave a square isotopic to C_{p}, so we need only examine the second. By Lemma 5 it suffices to show that the transpose of the square S′ defined by setting n = p in (2) is pan-Hamiltonian. Let M be the Latin square in which M_{ij} ≡ i − j + 1 (mod p), so that S′ is nearly a copy of M. We need to show that any two columns a and b of S′ consist of a single column cycle; something we know is true in M because M is isotopic to C_{p}. We split into two cases.

Case 1. 1 < a < b

Consider 2-regular bipartite graphs with vertices r_{1}, …, r_{p} and s_{1}, …, s_{p} corresponding to the rows and symbols respectively. When such a graph is made from the entries in columns a and b of M, let the graph be called G and when the columns a and b of S′ are used, let the graph be G′. Then G′ is obtained from G by removing four edges r_{a}s_{1}, r_{2a−1}s_{a}, r_{b}s_{1} and r_{2b−1}s_{b}, and replacing them with r_{a}s_{a}, r_{2a−1}s_{1}, r_{b}s_{b} and r_{2b−1}s_{1}. As already noted, G must be a single cycle. Orient it so that as we traverse it clockwise we encounter in order r_{a}, s_{1} then r_{b}. We next establish the order in which the crucial edges r_{2a−1}s_{a} and r_{2b−1}s_{b} will be encountered as we traverse G clockwise from r_{b}. By the symmetry inherent in M we know that the clockwise distance from r_{i} to s_{i} around G cannot depend on i. It follows that on our transversal we cannot encounter r_{b}, s_{b}, s_{a}, r_{a} in that order, so we must reach the edge r_{2a−1}s_{a} before r_{2b−1}s_{b}. Similarly the orientation of the edge r_{a}s_{1} determines that we must reach r_{2a−1} before s_{a} and the orientation of the edge r_{b}s_{1} determines that we must reach s_{b} before r_{2b−1}. In short, we must have the situation depicted in Figure 1(a). It is then clear (see Figure 1(b)) that G′ is also a single cycle.

Figure 1(a): G in case 1 Figure 1(b): G′ in case 1

Case 2. 1 = a < b

This time we let G be the graph formed by the union of the first column of S′ with column b of M, while G′ comes from columns 1 and b of S′. Note that G′ can be obtained from G by deleting the edges r_{b}s_{1} and r_{2b−1}s_{b} and replacing them with r_{b}s_{b} and r_{2b−1}s_{1}.

Consider a function f from the symbol set to itself which maps S′_{i1} to S′_{ib} for each i. Then f(x) ≡ 2x − b (mod p). Let f^{m} be f composed with itself m times, so that f^{m}(x) ≡ 2^{m}x − (2^{m} − 1)b. We look for fixed points of f^{m}. Note that f^{m}(x) = x if and only if (2^{m} −1)(x−b) ≡ 0 (mod p). Here is where we use the assumption that 2 is primitive modulo p and hence 2^{m} − 1 ≡ 0 (mod p) only if p − 1|m. Translating this knowledge, we see that our graph G consists of precisely two cycles, one of which is a digon on the vertices r_{2b−1} and s_{b}. It is then obvious (Figure 2) that the surgery performed to create G′ from G cannot fail to create a single cycle. ⊙

Figure 2(a): G in case 2 Figure 2(b): G′ in case 2

With regard to this last result, it is of interest to note that in the cases when 2 is not a primitive root modulo p, the graph G in Figure 2(a) consists of at least 3 cycles and hence G′ cannot be a single cycle. It follows that our construction never gives an atomic square in such a case. However it does give a square which is nearly atomic. All row cycles are Hamiltonian and only column cycles involving the first column fail to be Hamiltonian (a similar statement holds for the symbol cycles).

We can use Lemma 10 to screen our catalogue in §6 for atomic squares. The conclusion is that there are no atomic squares of order below 11 except those arising from groups of prime order. Note that Lemma 11 allows us to construct an atomic square of order 11 different from C_{11}.

Finally we note that atomic squares of composite orders do exist. For example, it is possible to create an atomic square of order 27 by applying the process described in §3 to the perfect 1-factorisation of K_{28} described in [3]. It would be of some interest to find an atomic square of an order which is not a prime power. No such square is known to the author.

§5. Transversal designs

A number of our results can be neatly expressed in terms of transversal designs (thanks to the referee for making this observation). A transversal design T D(n, k) is a set of nk points partitioned into k groups of n elements each, together with a set of blocks. Each block must contain exactly one point from each group and any two points from different groups must occur in exactly one block. It is well known that Latin squares can be formed from a T D(n, 3). Simply choose a correspondence from the three groups, in some order, to the rows, columns and symbols; then each of the n^{2} blocks designates a symbol to be placed in a particular row and column. Any two squares derived in this manner from the same transversal design will be in the same main class. More generally, a T D(n, k) is really just a set of k − 2 mutually orthogonal Latin squares by another name [4].

Suppose we are given T, a T D(n, 3) with groups G_{1}, G_{2} and G_{3}. For each point p ∈ G_{1} there is a 1-factor between G_{2} and G_{3} given by the restriction to G_{2} ∪ G_{3} of all the blocks containing p. Similarly, if two points p_{1}, p_{2} ∈ G_{1} are chosen, then they induce a 2-factor on G_{2} ∪ G_{3}. If this 2-factor is always a Hamiltonian cycle regardless of the choice of p_{1}, p_{2} then T corresponds to a pan-Hamiltonian Latin square (provided G_{1} is chosen to represent the rows). We might say that T is pan-Hamiltonian with respect to G_{1}. Of course, if T is pan-Hamiltonian with respect to all of its groups then T corresponds to an atomic square. In this case we say that T is an atomic transversal design (ATD).

Translating earlier results into the new terminology we find that an AT D(n, 3) cannot exist if n > 2 is even (Lemma 6), but that there is an AT D(p, 3) for all prime p (Lemma 4).

Indeed we can construct non-isomorphic AT D(p, 3) for many primes p (Lemma 11). We also know that an AT D(27, 3) exists but, as we will discover in the next section, an AT D(9, 3) does not.

One bonus from choosing the transversal design formulation is that it allows an immediate generalisation. We can define a T D(n, k) to be an AT D(n, k) if its projection onto any 3 of its groups yields an AT D(n, 3). However, the only such designs known at this stage for k > 3 arise from the Desarguesian projective planes of prime order p. Such planes yield an AT D(p, p + 1) in which every restriction to 3 groups is atomic because it is isomorphic to C_{p}. Hence we have a generalisation of Lemma 4.

§6. Small orders

For n ∈ {2, 3, 5} the catalogue of Latin squares in [5] shows that there is a single main class of N_{∞} square of order n, namely that of C_{n}. According to Norton [11] (notwithstanding the later correction by Sade [12]) there are precisely two main classes of N_{2} squares of order 7. Both turn out to be N_{∞} and to contain pan-Hamiltonian squares. An example from the main class other than that of C_{7} is:

A_{7} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 3 & 4 & 5 & 6 & 7 & 1 \\ 3 & 4 & 5 & 6 & 7 & 1 & 2 \\ 4 & 6 & 7 & 2 & 1 & 3 & 5 \\ 5 & 7 & 2 & 1 & 3 & 4 & 6 \\ 6 & 5 & 1 & 7 & 4 & 2 & 3 \\ 7 & 1 & 6 & 3 & 2 & 5 & 4 \end{matrix} ) .  (3)

We note that ν(A_{7}) = 2 and that A_{7} is isotopic to R^{−1}(A_{7}).

There are 37 main classes M containing pan-Hamiltonian Latin squares of order 9. In each case ν(M) = 2. Two examples are:

A_{9} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 2 & 4 & 1 & 5 & 7 & 9 & 8 & 6 & 3 \\ 3 & 8 & 9 & 2 & 4 & 5 & 6 & 1 & 7 \\ 4 & 9 & 2 & 3 & 1 & 8 & 5 & 7 & 6 \\ 5 & 3 & 8 & 1 & 6 & 7 & 9 & 4 & 2 \\ 6 & 5 & 7 & 8 & 9 & 4 & 2 & 3 & 1 \\ 7 & 1 & 5 & 6 & 8 & 2 & 3 & 9 & 4 \\ 8 & 7 & 6 & 9 & 3 & 1 & 4 & 2 & 5 \\ 9 & 6 & 4 & 7 & 2 & 3 & 1 & 5 & 8 \end{matrix} ) , B_{9} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 2 & 4 & 1 & 9 & 3 & 8 & 6 & 5 & 7 \\ 3 & 1 & 7 & 6 & 8 & 9 & 5 & 4 & 2 \\ 4 & 3 & 5 & 7 & 1 & 2 & 8 & 9 & 6 \\ 5 & 8 & 2 & 1 & 9 & 7 & 4 & 6 & 3 \\ 6 & 9 & 4 & 8 & 7 & 5 & 3 & 2 & 1 \\ 7 & 6 & 8 & 5 & 2 & 3 & 9 & 1 & 4 \\ 8 & 7 & 9 & 2 & 6 & 4 & 1 & 3 & 5 \\ 9 & 5 & 6 & 3 & 4 & 1 & 2 & 7 & 8 \end{matrix} ) . (4)

We intend to give an entire catalogue, but the above format is impractically bulky. Instead, we describe a Latin square using a single line of text. We do this by first reducing

the electronic journal of combinatorics 6 (1999), #R9 13

the square (that is, putting its first row and column in natural order). Then since the first row and column are known, we omit them. For the other rows, we write the remaining entries out in order from left to right, but without spaces. We process the rows from top to bottom, placing a dot between rows. The first part of the list looks like this:

41579863 · 89245617 · 92318576 · 38167942 · 57894231 · 15682394 · 76931425 · 64723158, 41963857 · 82147965 · 17629538 · 94832671 · 58794213 · 65281394 · 79315426 · 36578142, 41689537 · 52197846 · 86712395 · 64873912 · 17935428 · 39248651 · 95361274 · 78524163, 41785936 · 52947168 · 85372691 · 67891423 · 19523847 · 38169254 · 96214375 · 74638512, 41768935 · 17924658 · 98235176 · 64879321 · 79513842 · 86392514 · 35641297 · 52187463, 51689347 · 19578624 · 62817935 · 97124863 · 85743291 · 36295418 · 74932156 · 48361572, 41679358 · 17824695 · 56291837 · 38947162 · 85712943 · 69583421 · 94135276 · 72368514, 46587193 · 14962578 · 65329817 · 87134962 · 58793241 · 39218456 · 91675324 · 72841635, 41975836 · 78629451 · 92813675 · 39764218 · 54198327 · 15382964 · 67241593 · 86537142, 41835697 · 62987541 · 97368215 · 74129863 · 89513472 · 15642938 · 56791324 · 38274156.

The lines above represent ten pan-Hamiltonian Latin squares (one per line) in the condensed format described. Each of these ten squares is isotopic to its row inverse. In the other 27 main classes (listed below) there is no such symmetry. Note that A_{9}, B_{9} in (4) are respectively the first square in the list above and the first square in the list below.

41938657 · 17689542 · 35712896 · 82197463 · 94875321 · 68523914 · 79264135 · 56341278, 51679438 · 75124896 · 12895367 · 68937142 · 34582971 · 96248513 · 49713625 · 87361254, 41598376 · 52879614 · 97613258 · 16947823 · 39285147 · 85362491 · 64721935 · 78134562, 41895673 · 69148257 · 17389562 · 84723196 · 92574831 · 35612948 · 76931425 · 58267314, 41795638 · 69271845 · 17328956 · 74983162 · 82539417 · 95864321 · 56147293 · 38612574, 41567938 · 95748216 · 17395862 · 64829173 · 82973451 · 38214695 · 79631524 · 56182347, 51648973 · 98167254 · 62789531 · 19274368 · 74923815 · 35812496 · 46395127 · 87531642, 46379158 · 18924567 · 82795613 · 69187432 · 71238945 · 35841296 · 94562371 · 57613824, 46879135 · 14792568 · 85627913 · 78963421 · 39214857 · 61538294 · 92145376 · 57381642, 48569173 · 19842567 · 56971832 · 67123948 · 95387421 · 34618295 · 71294356 · 82735614, 51649837 · 46875912 · 62937158 · 79182364 · 87314295 · 35298641 · 94761523 · 18523476, 51897364 · 76948152 · 62719835 · 38271496 · 19534278 · 84625913 · 97362541 · 45183627,

the electronic journal of combinatorics 6 (1999), #R9 14

41695837 · 59781264 · 38529671 · 87364912 · 94172358 · 12843596 · 65917423 · 76238145, 41567893 · 54872961 · 76985312 · 68391274 · 92138457 · 15249638 · 39714526 · 87623145, 41983675 · 95271468 · 17825936 · 89362147 · 34597821 · 58649213 · 76134592 · 62718354, 41763895 · 69218457 · 17829563 · 76984321 · 94572138 · 82395614 · 35641972 · 58137246, 51384697 · 48697521 · 62738915 · 37921846 · 89513472 · 16249358 · 94175263 · 75862134, 41637895 · 17948652 · 68571923 · 92863174 · 54189237 · 39215468 · 76392541 · 85724316, 51789364 · 86912547 · 62831975 · 37248691 · 78395412 · 19524836 · 94167253 · 45673128, 47935168 · 18692574 · 62319857 · 84273916 · 59847231 · 91568423 · 76124395 · 35781642, 51748936 · 85697142 · 62931857 · 49163278 · 38275491 · 14829365 · 97514623 · 76382514, 41739865 · 78691524 · 52978136 · 86342971 · 39517248 · 15864392 · 94123657 · 67285413, 41739658 · 84961572 · 37815926 · 69348217 · 92173845 · 15682394 · 56297431 · 78524163, 48963175 · 17689542 · 59712368 · 86274913 · 34897251 · 62531894 · 91345627 · 75128436, 41583976 · 86914257 · 39725618 · 64897123 · 97248531 · 15362894 · 72139465 · 58671342, 45967138 · 16728594 · 59613827 · 97281643 · 34879215 · 68194352 · 72345961 · 81532476, 47639158 · 14768592 · 68971325 · 39124867 · 85397241 · 56812934 · 91245673 · 72583416.

We close this section by comparing our theoretical results from earlier sections with the data from orders up to 9. Firstly, we expect from Lemma 7 to be able to construct pan-Hamiltonian squares of order n from any perfect 1-factorisation of K_{n+1}. Indeed, Lemma 8 shows that we may be able to construct more than one main class starting from a given 1-factorisation. However, all squares constructed in this way will have the symmetry that the square is isotopic to its row inverse. For n = 7, Lemma 8 predicts (at least) two distinct squares, and the squares constructed there are easily seen to be isotopic to C_{7} and the square A_{7} given in (3).

For n = 9, Lemma 9 predicts at least one main class of pan-Hamiltonian square derived from a perfect 1-factorisation of K_{10}. In fact there is only one such 1-factorisation [14] and unlike the n = 7 case, it produces a single main class. A representative of this class is A_{9} as given in (4).

§7. Other N_{∞} squares of order 9.

We saw in §6 that all main classes of N_{∞} squares of odd order less than 9 contain a pan-Hamiltonian square. In contrast, a minority of main classes of N_{∞} squares of order 9 have this property. We show this by looking at the subsquare structure of all N_{2} squares of order 9, using a catalogue of the 1707 main classes of such square [10]. (The lists in §6 were also prepared from this catalogue.) Since a Latin square cannot have a proper subsquare of more than half its order and there are no N_{2} squares of order 4, we conclude that N_{2} squares of order 9 cannot have proper subsquares except of order 3. The breakdown of the 1707 main classes according to the number of order 3 subsquares appears in Table 1. For each main class the number of reduced squares in that class was calculated, and these totals are also given. (A Latin square of order n is reduced if the entries in its first row and column are in the natural order 1, 2, 3, …, n. The total number of squares is a factor of n!(n − 1)! larger than the number of reduced squares.)

Order 3 subsquares  Main classes  Reduced squares
0  1589  28854493920
1  46  550851840
2  1  9797760
3  15  123016320
4  3  8164800
6  5  18779040
9  24  33653760
10  9  46267200
12  11  14152320
18  3  453600
36  1  840
Total  1707  29659631400

Table 1: Subsquares of N_{2} squares of order 9.

In particular we note that there are 1589 main classes of N_{∞} squares of order 9, yet only 37 of these contain pan-Hamiltonian squares. In terms of reduced squares, there are 28854493920 N_{∞} squares and ‘only’ 426746880 which are pan-Hamiltonian (or have a conjugate which is pan-Hamiltonian).

§8. References

[1] L. D. Andersen, Factorizations of graphs, The CRC handbook of combinatorial designs (Eds: C. J. Colbourn and J. H. Dinitz), CRC Press, Boca Raton, FL, 1996, 653–667.

[2] L. D. Andersen and E. Mendelsohn, A direct construction for Latin squares without proper subsquares, Ann. Discrete Math. 15 (1982) 27–53.

[3] B. A. Anderson, A class of starter induced one-factorisations, Lecture notes in math. 406 (1974) 180–185.

[4] A. E. Brouwer, Block designs, Handbook of combinatorics (Eds: R. L. Graham, M. Grötschel and L. Lovász), Elsevier, Amsterdam, 1995, 693–745.

[5] J. Dénes and A. D. Keedwell, Latin squares and their applications, Akadémiai Kiadó, Budapest, 1974.

[6] J. Dénes and A. D. Keedwell, Latin squares: New developments in the theory and applications, Annals Discrete Math. 46, North-Holland, Amsterdam, 1991.

[7] P. B. Gibbons and E. Mendelsohn, The existence of a subsquare free Latin square of side 12, SIAM J. Algebraic Discrete Methods 8 (1987) 93–99.

[8] K. Heinrich, Latin squares with no proper subsquares, J. Comb. Th. Ser. A 29 (1980) 346–353.

[9] A. J. W. Hilton and C. A. Rodger, Hamiltonian double Latin squares, preprint.

[10] B. D. McKay, private communication.

[11] H. W. Norton, The 7 × 7 squares, Ann. Eugenics 9 (1939) 269–307.

[12] A. Sade, An omission in Norton’s list of 7 × 7 squares, Ann. Math. Statist. 22 (1951) 306–307.

[13] S. Stein, MR 82b05032, Mathematical reviews (1982) 486.

[14] W. D. Wallis, One-factorizations, Kluwer Academic, Dordrecht, Netherlands, 1997.