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     

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     

Generalized Latin squares and their defining sets

A generalized Latin square of type (n,k) is an n×n array of symbols 1,2,…,k such that each of these symbols occurs at most once in each row and each column. Let d(n,k) denote the cardinality of the minimal set S of given entries of an n×n array such that there exists a unique extension of S to a generalized Latin square of type (n,k). In this paper we discuss the properties of d(n,k) for k=2n-1 and k=2n-2. We give an alternate proof of the identity d(n,2n-1)=n²-n, which holds for even n, and we establish the new result . We also show that the latter bound is tight for n divisible by 10.     

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.     

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     

Mutually orthogonal equitable Latin rectangles

Let ab=n². We define an equitable Latin rectangle as an a×b matrix on a set of n symbols where each symbol appears either or times in each row of the matrix and either or times in each column of the matrix. Two equitable Latin rectangles are orthogonal in the usual way. Denote a set of ka×b mutually orthogonal equitable Latin rectangles as a k– MOELR (a,b;n). When a≠9,18,36, or 100, then we show that the maximum number of k– MOELR (a,b;n)≥3 for all possible values of (a,b).     

Minimal homogeneous latin trades

A latin trade is a subset of a latin square which may be replaced with a disjoint mate to obtain a new latin square. A d-homogeneous latin trade is one which intersects each row, each column and each entry of the latin square either 0 or d times. In this paper we give a construction for minimal d-homogeneous latin trades of size dm, for every integer d?3, and m?1.75d²+3. We also improve this bound for small values of d. Our proof relies on the construction of cyclic sequences whose adjacent sums are distinct.     

On the separation power and the completion of partial latin squares

Let n and m be natural numbers, n ? m. The separation power of order n and degree m is the largest integer k = k(n, m) such that for every (0, 1)-matrix A of order n with constant linesums equal to m and any set of k 1's in A there exist (disjoint) permutation matrices P₁,…, P_m such that A = P₁ + … + P_m and each of the k 1's lies in a different P_i. Almost immediately we have 1 ? k(n, m) ? m ? 1, yet in all cases where the value of k(n, m) is actually known it equals m ? 1 (except under the somewhat trivial circumstances of k(n, m) = 1). This leads to a conjecture about the separation power, namely that k(n, m) = m ? 1 if $\text{m ? [}\text{n}\text{2}\text{] + 1}$. We obtain the bound $\text{k(n, m) ? m ? [}\text{n}\text{2}\text{] + 2}$, so that this conjecture holds for n ? 7. We then move on to latin squares, describing several equivalent formulations of the concept. After establishing a sufficient condition for the completion of a partial latin square in terms of the separation power, we can show that the Evans conjecture follows from this conjecture about the separation power. Finally the lower bound on k(n, m) allows us to show, after some calculations, that the Evans conjecture is true for orders n ? 11.     

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     

On the number of transversals in Cayley tables of cyclic groups

It is well known that if n is even, the addition table for the integers modulo n (which we denote by B_n) possesses no transversals. We show that if n is odd, then the number of transversals in B_n is at least exponential in n. Equivalently, for odd n, the number of diagonally cyclic latin squares of order n, the number of complete mappings or orthomorphisms of the cyclic group of order n, the number of magic juggling sequences of period n and the number of placements of n non-attacking semi-queens on an n×n toroidal chessboard are at least exponential in n. For all large n we show that there is a latin square of order n with at least (3.246)ⁿ transversals.We diagnose all possible sizes for the intersection of two transversals in B_n and use this result to complete the spectrum of possible sizes of homogeneous latin bitrades.We also briefly explore potential applications of our results in constructing random mutually orthogonal latin squares.     

Latin squares with no small odd plexes

A k‐plex in a Latin square of order n is a selection of kn entries in which each row, column, and symbol is represented precisely k times. A transversal of a Latin square corresponds to the case k = 1. We show that for all even n > 2 there exists a Latin square of order n which has no k‐plex for any odd but does have a k‐plex for every other . © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 477–492, 2008     

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.     

Latin squares with bounded size of row prefix intersections

A latin square is a matrix of size n×n with entries from the set {1,…,n}, such that each row and each column is a permutation on {1,…,n}. We show how to construct a latin square such that for any two distinct rows, the prefixes of length h of the two rows share at most about h²/n elements. This upper bound is close to optimal when contrasted with a lower bound derived from the Second Johnson bound [6].     

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.     

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     

All group‐based latin squares possess near transversals

In a latin square of order n, a near transversal is a collection of n ?1 cells which intersects each row, column, and symbol class at most once. A longstanding conjecture of Brualdi, Ryser, and Stein asserts that every latin square possesses a near transversal. We show that this conjecture is true for every latin square that is main class equivalent to the Cayley table of a finite group.     

A product theorem for row-complete Latin squares

In this article it is shown how to construct a row-complete latin square of order mn, given one of order m and given a sequencing of a group of ordern. This yields infinitely many new orders for which row-complete latin squares can be constructed. © 1997 John Wiley & Sons, Inc. J Combin Designs 5: 311–318, 1997     

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.     

Monogamous latin squares

We show for all n∉{1,2,4} that there exists a latin square of order n that contains two entries γ₁ and γ₂ such that there are some transversals through γ₁ but they all include γ₂ as well. We use this result to show that if n>6 and n is not of the form 2p for a prime p?11 then there exists a latin square of order n that possesses an orthogonal mate but is not in any triple of MOLS. Such examples provide pairs of 2-maxMOLS.     

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