Latin Squares, Partial Latin Squares and Their Generalized Quotients

A (partial) Latin square is a table of multiplication of a (partial) quasigroup. Multiplication of a (partial) quasigroup may be considered as a set of triples. We give a necessary and sufficient condition for a set of triples to be a quotient of a (partial) Latin square. Received: April, 2003     

Partial Latin Squares Are Avoidable

A square array is avoidable if for each set of n symbols there is an n × n Latin square on these symbols which differs from the array in every cell. The main result of this paper is that for m ≥ 2 any partial Latin square of order 4m − 1 is avoidable, thus concluding the proof that any partial Latin square of order at least 4 is avoidable.     

Completions of ‐Dense Partial Latin Squares

A classical question in combinatorics is the following: given a partial Latin square P, when can we complete P to a Latin square L? In this paper, we investigate the class of ε‐dense partial Latin squares: partial Latin squares in which each symbol, row, and column contains no more than ‐many nonblank cells. Based on a conjecture of Nash‐Williams, Daykin and Häggkvist conjectured that all ‐dense partial Latin squares are completable. In this paper, we will discuss the proof methods and results used in previous attempts to resolve this conjecture, introduce a novel technique derived from a paper by Jacobson and Matthews on generating random Latin squares, and use this technique to study ε‐dense partial Latin squares that contain no more than filled cells in total. In this paper, we construct completions for all ε‐dense partial Latin squares containing no more than filled cells in total, given that . In particular, we show that all ‐dense partial Latin squares are completable. These results improve prior work by Gustavsson, which required , as well as Chetwynd and Häggkvist, which required , n even and greater than 10⁷.     

Nowhere-Zero 4-Flows,Simultaneous Edge-Colorings,And Critical Partial Latin Squares

It is proved in this paper that every bipartite graphic sequence with the minimum degree 2 has a realization that admits a nowhere-zero 4-flow. This result implies a conjecture originally proposed by Keedwell (1993) and reproposed by Cameron (1999) about simultaneous edge-colorings and critical partial Latin squares.* Partially supported by RGC grant HKU7054/03P. Partially supported by the National Security Agency under Grants MDA904-00-1-00614 and MDA904-01-1-0022.     

On Non-Polynomial Latin Squares

It turns out that Latin squares which are hard to approximate by a polynomial are suitable to be used as a part of block cipher algorithms (BCA). In this paper we state basic properties of those Latin squares and provide their construction.     

Latin Squares without Orthogonal Mates

In 1779 Euler proved that for every even n there exists a latin square of order n that has no orthogonal mate, and in 1944 Mann proved that for every n of the form 4k + 1, k ≥ 1, there exists a latin square of order n that has no orthogonal mate. Except for the two smallest cases, n = 3 and n = 7, it is not known whether a latin square of order n = 4k + 3 with no orthogonal mate exists or not. We complete the determination of all n for which there exists a mate-less latin square of order n by proving that, with the exception of n = 3, for all n = 4k + 3 there exists a latin square of order n with no orthogonal mate. We will also show how the methods used in this paper can be applied more generally by deriving several earlier non-orthogonality results.     

Latin Squares with Restricted Transversals

The original article to which this erratum refers was correctly published online on 1 December 2011. Due to an error at the publisher, it was then published in Journal of Combinatorial Designs 20: 124–141, 2012 without the required shading in several examples. To correct this, the article is here reprinted in full. The publisher regrets this error. We prove that for all odd there exists a latin square of order 3m that contains an latin subrectangle consisting of entries not in any transversal. We prove that for all even there exists a latin square of order n in which there is at least one transversal, but all transversals coincide on a single entry. A corollary is a new proof of the existence of a latin square without an orthogonal mate, for all odd orders . Finally, we report on an extensive computational study of transversal‐free entries and sets of disjoint transversals in the latin squares of order . In particular, we count the number of species of each order that possess an orthogonal mate. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 20: 344–361, 2012     

Cycle Switches in Latin Squares

Cycle switches are the simplest changes which can be used to alter latin squares, and as such have found many applications in the generation of latin squares. They also provide the simplest examples of latin interchanges or trades in latin square designs. In this paper we construct graphs in which the vertices are classes of latin squares. Edges arise from switching cycles to move from one class to another. Such graphs are constructed on sets of isotopy or main classes of latin squares for orders up to and including eight. Variants considered are when (i) only intercalates may be switched, (ii) any row cycle may be switched and (iii) all cycles may be switched. The structure of these graphs reveals special roles played by N₂, pan-Hamiltonian, atomic, semi-symmetric and totally symmetric latin squares. In some of the graphs parity is important because, for example, the odd latin squares may be disconnected from the even latin squares. An application of our results to the compact storage of large catalogues of latin squares is discussed. We also prove lower bounds on the number of cycles in latin squares of both even and odd orders and show these bounds are sharp for infinitely many orders.This work was undertaken while the author was employed by Christ Church, Oxford, UK     

On the Number of Latin Squares

We (1) determine the number of Latin rectangles with 11 columns and each possible number of rows, including the Latin squares of order 11, (2) answer some questions of Alter by showing that the number of reduced Latin squares of order n is divisible by f! where f is a particular integer close to (3) provide a formula for the number of Latin squares in terms of permanents of (+1, −1)-matrices, (4) find the extremal values for the number of 1-factorisations of k-regular bipartite graphs on 2n vertices whenever 1 ≤ k ≤ n ≤ 11, (5) show that the proportion of Latin squares with a non-trivial symmetry group tends quickly to zero as the order increases. Received September 3, 2004     

On Parity Vectors of Latin Squares

The parity vectors of two Latin squares of the same side n provide a necessary condition for the two squares to be biembeddable in an orientable surface. We investigate constraints on the parity vector of a Latin square resulting from structural properties of the square, and show how the parity vector of a direct product may be obtained from the parity vectors of the constituent factors. Parity vectors for Cayley tables of all Abelian groups, some non-Abelian groups, Steiner quasigroups and Steiner loops are determined. Finally, we give a lower bound on the number of main classes of Latin squares of side n that admit no self-embeddings.     

Autoparatopisms of Quasigroups and Latin Squares

Paratopism is a well‐known action of the wreath product on Latin squares of order n. A paratopism that maps a Latin square to itself is an autoparatopism of that Latin square. Let Par(n) denote the set of paratopisms that are an autoparatopism of at least one Latin square of order n. We prove a number of general properties of autoparatopisms. Applying these results, we determine Par(n) for . We also study the proportion of all paratopisms that are in Par(n) as .     

Permanents and Determinants of Latin Squares

Let L be a latin square of indeterminates. We explore the determinant and permanent of L and show that a number of properties of L can be recovered from the polynomials and per(L). For example, it is possible to tell how many transversals L has from per(L), and the number of 2 × 2 latin subsquares in L can be determined from both and per(L). More generally, we can diagnose from or per(L) the lengths of all symbol cycles. These cycle lengths provide a formula for the coefficient of each monomial in and per(L) that involves only two different indeterminates. Latin squares A and B are trisotopic if B can be obtained from A by permuting rows, permuting columns, permuting symbols, and/or transposing. We show that nontrisotopic latin squares with equal permanents and equal determinants exist for all orders that are divisible by 3. We also show that the permanent, together with knowledge of the identity element, distinguishes Cayley tables of finite groups from each other. A similar result for determinants was already known.     

Latin Squares with a Unique Intercalate

Suppose that and . We construct a Latin square of order n with the following properties:

• has no proper subsquares of order 3 or more .
• has exactly one intercalate (subsquare of order 2) .
• When the intercalate is replaced by the other possible subsquare on the same symbols, the resulting Latin square is in the same species as .

Hence generalizes the square that Sade famously found to complete Norton's enumeration of Latin squares of order 7. In particular, is what is known as a self‐switching Latin square and possesses a near‐autoparatopism.     

Some results on generalized Latin Squares

We prove several results on the extension of partial generalized Latin Squares under various constraints.     

Latin Squares and the Hall-Paige Conjecture

The Hall–Paige conjecture deals with conditions underwhich a finite group G will possess a complete mapping, or equivalentlya Latin square based on the Cayley table of G will possess atransversal. Two necessary conditions are known to be: (i) thatthe Sylow 2-subgroups of G are trivial or non-cyclic, and (ii)that there is some ordering of the elements of G which yieldsa trivial product. These two conditions are known to be equivalent,but the first direct, elementary proof that (i) implies (ii)is given here. It is also shown that the Hall–Paige conjecture impliesthe existence of a duplex in every group table, thereby provinga special case of Rodney's conjecture that every Latin squarecontains a duplex. A duplex is a ‘double transversal’,that is, a set of 2n entries in a Latin square of order n suchthat each row, column and symbol is represented exactly twice.2000 Mathematics Subject Classification 05B15, 20D60.     

Difference Covering Arrays and Pseudo-Orthogonal Latin Squares

A pair of Latin squares, A and B, of order n, is said to be pseudo-orthogonal if each symbol in A is paired with every symbol in B precisely once, except for one symbol with which it is paired twice and one symbol with which it is not paired at all. A set of t Latin squares, of order n, are said to be mutually pseudo-orthogonal if they are pairwise pseudo-orthogonal. A special class of pseudo-orthogonal Latin squares are the mutually nearly orthogonal Latin squares (MNOLS) first discussed in 2002, with general constructions given in 2007. In this paper we develop row complete MNOLS from difference covering arrays. We will use this connection to settle the spectrum question for sets of 3 mutually pseudo-orthogonal Latin squares of even order, for all but the order 146.