Latin squares with restricted transversals

We prove that for all odd m ≥ 3 there exists a latin square of order 3 m that contains an ( m ? 1 ) × m latin subrectangle consisting of entries not in any transversal. We prove that for all even n ≥ 10 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 n ≥ 11 . Finally, we report on an extensive computational study of transversal‐free entries and sets of disjoint transversals in the latin squares of order n ? 9 . In particular, we count the number of species of each order that possess an orthogonal mate. © 2011 Wiley Periodicals, Inc. J Combin Designs 20:124‐141, 2012     

Construction of doubly diagonalized orthogonal latin squares

A transversal T of a latin square is a collection of n cells no two in the same row or column and such that each of the integers 1, 2, …, n appears in exactly one of the cells of T. A latin square is doubly diagonalized provided that both its main diagonal and off-diagonal are transversals. Although it is known that a doubly diagonalized latin square of every order n ≥ 4 exists and that a pair of orthogonal latin squares of order n exists for every n ≠ 2 or 6, it is still an open question as to what the spectrum is for pairs of doubly diagonalized orthogonal latin squares. The best general result seems to be that pairs of orthogonal doubly diagonalized latin squares of order n exist whenever n is odd or a multiple of 4, except possibly when n is a multiple of 3 but not of 9. In this paper we give a new construction for doubly diagonalized latin squares which is used to enlarge the known class for doubly diagonalized orthogonal squares. The construction is based on Sade's singular direct product of quasigroups.     

Bachelor latin squares with large indivisible plexes

In a latin square of order n , a k ‐plex is a selection of kn entries in which each row, column, and symbol occurs k times. A 1 ‐plex is also called a transversal. A k ‐plex is indivisible if it contains no c ‐plex for 0 < c < k . We prove that, for all n ≥ 4 , there exists a latin square of order n that can be partitioned into an indivisible ? n / 2 ?‐plex and a disjoint indivisible ? n / 2 ?‐plex. For all n ≥ 3 , we prove that there exists a latin square of order n with two disjoint indivisible ? n / 2 ?‐plexes. We also give a short new proof that, for all odd n ≥ 5 , there exists a latin square of order n with at least one entry not in any transversal. Such latin squares have no orthogonal mate. Copyright © 2011 Wiley Periodicals, Inc. J Combin Designs 19:304‐312, 2011     

The recognition of symmetric latin squares

A latin square S is isotopic to another latin square S′ if S′ can be obtained from S by permuting the row indices, the column indices and the symbols in S. Because the three permutations used above may all be different, a latin square which is isotopic to a symmetric latin square need not be symmetric. We call the problem of determining whether a latin square is isotopic to a symmetric latin square the symmetry recognition problem. It is the purpose of this article to give a solution to this problem. For this purpose we will introduce a cocycle corresponding to a latin square which transforms very simply under isotopy, and we show this cocycle contains all the information needed to determine whether a latin square is isotopic to a symmetric latin square. Our results relate to 1‐factorizations of the complete graph on n + 1 vertices, K_{n + 1}. There is a well known construction which can be used to make an n × n latin square from a 1‐factorization on n + 1 vertices. The symmetric idempotent latin squares are exactly the latin squares that result from this construction. The idempotent recognition problem is simple for symmetric latin squares, so our results enable us to recognize exactly which latin squares arise from 1‐factorizations of K_{n + 1}. As an example we show that the patterned starter 1‐factorization for the group G gives rise to a latin square which is in the main class of the Cayley latin square for G if and only if G is abelian. Hence, every non‐abelian group gives rise to two latin squares in different main classes. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 291–300, 2008     

Symmetric latin square and complete graph analogues of the evans conjecture

With the proof of the Evans conjecture, it was established that any partial latin square of side n with a most n ? 1 nonempty cells can be completed to a latin square of side n. In this article we prove an analogous result for symmetric latin squares: a partial symmetric latin square of side n with an admissible diagonal and at most n ? 1 nonempty cells can be completed to a symmetric latin square of side n. We also characterize those partial symmetric latin squares of side n with exactly n or n + 1 nonempty cells which cannot be completed. From these results we deduce theorems about completing edge-colorings of complete graphs K_2m and K_{2m ? 1} with 2m ? 1 colors, with m + 1 or fewer edges getting prescribed colors. © 1994 John Wiley & Sons, Inc.     

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.     

Transversals and multicolored matchings

Ryser conjectured that the number of transversals of a latin square of order n is congruent to n modulo 2. Balasubramanian has shown that the number of transversals of a latin square of even order is even. A 1‐factor of a latin square of order n is a set of n cells no two from the same row or the same column. We prove that for any latin square of order n, the number of 1‐factors with exactly n ? 1 distinct symbols is even. Also we prove that if the complete graph K_2n, n ≥ 8, is edge colored such that each color appears on at most edges, then there exists a multicolored perfect matching. © 2004 Wiley Periodicals, Inc.     

Row-complete latin squares of every composite order exist

A construction for a row-complete latin square of order n, where n is any odd composite number other than 9, is given in this article. Since row-complete latin squares of order 9 and of even order have previously been constructed, this proves that row-complete latin squares of every composite order exist. © 1998 John Wiley & Sons, Inc. J Combin Designs 6:63–77, 1998     

On the completion of partial latin squares

In this paper a certain condition on partial latin squares is shown to be sufficient to guarantee that the partial square can be completed, namely, that it have fewer than n entries, and that at most $\text{[}\text{(n + 1)}\text{2}\text{]}$ of these lie off some line, where n is the order of the square. This is applied to establish that the Evans conjecture is true for n ? 8; i.e., that given a partial latin square of order n with fewer than n entries, n ? 8, the square can be completed. Finally, the results are viewed in a conjugate way to establish different conditions sufficient for the completion of a partial latin square.     

A superlinear lower bound for the size of a critical set in a latin square

A critical set is a partial latin square that has a unique completion to a latin square, and is minimal with respect to this property. Let scs(n) denote the smallest possible size of a critical set in a latin square of order n. We show that for all n, . Thus scs(n) is superlinear with respect to n. We also show that scs(n) ≥ 2n?32 and if n ≥ 25, . © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 269–282, 2007     

On the spectrum of critical sets in latin squares of order 2n

Suppose that L is a latin square of order m and P ? L is a partial latin square. If L is the only latin square of order m which contains P, and no proper subset of P has this property, then P is a critical set of L. The critical set spectrum problem is to determine, for a given m, the set of integers t for which there exists a latin square of order m with a critical set of size t. We outline a partial solution to the critical set spectrum problem for latin squares of order 2ⁿ. The back circulant latin square of even order m has a well‐known critical set of size m²/4, and this is the smallest known critical set for a latin square of order m. The abelian 2‐group of order 2ⁿ has a critical set of size 4ⁿ‐3ⁿ, and this is the largest known critical set for a latin square of order 2ⁿ. We construct a set of latin squares with associated critical sets which are intermediate between the back circulant latin square of order 2ⁿ and the abelian 2‐group of order 2ⁿ. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 25–43, 2008     

Embedding a latin square in a pair of orthogonal latin squares

In this paper, it is shown that a latin square of order n with n ≥ 3 and n ≠ 6 can be embedded in a latin square of order n² which has an orthogonal mate. A similar result for idempotent latin squares is also presented. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 270–276, 2006     

Multi-latin squares

A multi-latin square of order n and index k is an n×n array of multisets, each of cardinality k, such that each symbol from a fixed set of size n occurs k times in each row and k times in each column. A multi-latin square of index k is also referred to as a k-latin square. A 1-latin square is equivalent to a latin square, so a multi-latin square can be thought of as a generalization of a latin square.In this note we show that any partially filled-in k-latin square of order m embeds in a k-latin square of order n, for each n≥2m, thus generalizing Evans’ Theorem. Exploiting this result, we show that there exist non-separable k-latin squares of order n for each n≥k+2. We also show that for each n≥1, there exists some finite value g(n) such that for all k≥g(n), every k-latin square of order n is separable.We discuss the connection between k-latin squares and related combinatorial objects such as orthogonal arrays, latin parallelepipeds, semi-latin squares and k-latin trades. We also enumerate and classify k-latin squares of small orders.     

Symmetries that latin squares inherit from 1‐factorizations

A 1‐factorization of a graph is a decomposition of the graph into edge disjoint perfect matchings. There is a well‐known method, which we call the ??‐construction, for building a 1‐factorization of K_n,n from a 1‐factorization of K_{n + 1}. The 1‐factorization of K_n,n can be written as a latin square of order n. The ??‐construction has been used, among other things, to make perfect 1‐factorizations, subsquare‐free latin squares, and atomic latin squares. This paper studies the relationship between the factorizations involved in the ??‐construction. In particular, we show how symmetries (automorphisms) of the starting factorization are inherited as symmetries by the end product, either as automorphisms of the factorization or as autotopies of the latin square. Suppose that the ??‐construction produces a latin square L from a 1‐factorization F of K_{n + 1}. We show that the main class of L determines the isomorphism class of F, although the converse is false. We also prove a number of restrictions on the symmetries (autotopies and paratopies) which L may possess, many of which are simple consequences of the fact that L must be symmetric (in the usual matrix sense) and idempotent. In some circumstances, these restrictions are tight enough to ensure that L has trivial autotopy group. Finally, we give a cubic time algorithm for deciding whether a main class of latin squares contains any square derived from the ??‐construction. The algorithm also detects symmetric squares and totally symmetric squares (latin squares that equal their six conjugates). © 2005 Wiley Periodicals, Inc. J Combin Designs 13: 157–172, 2005.     

The Existence of Latin Squares without Orthogonal Mates

A latin square is a bachelor square if it does not possess an orthogonal mate; equivalently, it does not have a decomposition into disjoint transversals. We define a latin square to be a confirmed bachelor square if it contains an entry through which there is no transversal. We prove the existence of confirmed bachelor squares for all orders greater than three. This resolves the existence question for bachelor squares.     

Orthogonal latin square graphs

An orthogonal latin square graph (OLSG) is one in which the vertices are latin squares of the same order and on the same symbols, and two vertices are adjacent if and only if the latin squares are orthogonal. If G is an arbitrary finite graph, we say that G is realizable as an OLSG if there is an OLSG isomorphic to G. The spectrum of G [Spec(G)] is defined as the set of all integers n that there is a realization of G by latin squares of order n. The two basic theorems proved here are (1) every graph is realizable and (2) for any graph G, Spec G contains all but a finite set of integers. A number of examples are given that point to a number of wide open questions. An example of such a question is how to classify the graphs for which a given n lies in the spectrum.     

Thwarts in transversal designs

A subset of points in a transversal design is athwart if each block in the design has one of a small number of intersection sizes with the subset. Applications to the construction of mutually orthogonal latin squares are given. One particular case involves inequalities for the minimum number of distinct symbols appearing in an × subarray of an×n latin square. Using thwarts, new transversal designs are determined for orders 408, 560, 600, 792, 856, 1046, 1059, 1368, 2164, 2328, 2424, 3288, 3448, 3960, 3992, 3994, 4025, 4056, 4824, 5496, 6264, 7768, 7800, 8096, and 9336.     

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     

A Note on Toeplitz’ Conjecture

In 1911, Toeplitz made a conjecture asserting that every Jordan curve in $\mathbb{R}^{2}$ contains four points forming the corners of a square. Here Conjecture C is presented, which states that the side length of the largest square on a closed curve that consists of edges of an n×n grid is at least $1/\sqrt{2}$ times the side length of the largest axis-aligned square contained inside the curve. Conjecture C implies Toeplitz’ conjecture and is verified computationally for n≤13.     

Longest Partial Transversals in Plexes

A k-protoplex of order n is a partial latin square of order n such that each row and column contains precisely k entries and each symbol occurs precisely k times. If a k-protoplex is completable to a latin square, then it is a k-plex. A 1-protoplex is a transversal. Let \({\phi_k}\) denote the smallest order for which there exists a k-protoplex that contains no transversal, and let \({{{\phi_k}^{*}}}\) denote the smallest order for which there exists a k-plex that contains no transversal. We show that \({k \leqslant \phi_k = {{\phi_k}^{*}} \leqslant k+1}\) for all \({k \geqslant 6}\) . Given a k-protoplex P of order n, we define T(P) to be the size of the largest partial transversal in P. We explore upper and lower bounds for T(P). Aharoni et al. have conjectured that \({T(P) \geqslant (k-1)n/k}\) . We find that $$T(P) > max \{ k(1-n^{-1/2}), k-n/(n-k), n-O (nk^{-1/2}log^{3/2} k)\}$$ . In the special case of 3-protoplexes, we improve the lower bound for T(P) to 3n/5.