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     

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     

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.     

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.     

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     

Avoiding multiple entry arrays

In this paper we consider the problem of avoiding arrays with more than one entry per cell. An n × n array on n symbols is said to be if an n × n latin square, on the same symbols, can be found which differs from the array in every cell. Our first result is for chessboard squares with at most two entries per black cell. We show that if k ≥ 1 and C is a 4k × 4k chessboard square on symbols 1, 2, …, 4k in which every black cell contains at most two symbols and every symbol appears at most once in every row and column, then C is avoidable. Our main result is for squares with at most two entries in any cell and answers a question of Hilton. If k 3240 and F is a 4k × 4k array on 1, 2,…, 4k in which every cell contains at most two symbols and every symbol appears at most twice in every row and column, then F is avoidable. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 257–266, 1997     

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     

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.     

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.     

Doubly diagonal orthogonal latin squares

A pair of doubly diagonal orthogonal latin squares of order n, DDOLS(n), is a pair of orthogonal latin squares of order n with the property that each square has a transversal on both the front diagonal (the cells {(i, i):1?i?n}) and the back diagonal (the cells {(i, n + 1?i): 1?i?n}). We show that for all n except n = 2, 3, 6, 10, 12, 14, 15, 18 and 26, there exists a pair of DDOLS(n). Obbviously these do not exist when n = 2, 3 and 6.     

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 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     

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.     

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     

Atomic Latin squares of order eleven

A Latin square is pan‐Hamiltonian if the permutation which defines row i relative to row j consists of a single cycle for every i ≠ j. A Latin square is atomic if all of its conjugates are pan‐Hamiltonian. We give a complete enumeration of atomic squares for order 11, the smallest order for which there are examples distinct from the cyclic group. We find that there are seven main classes, including the three that were previously known. A perfect 1‐factorization of a graph is a decomposition of that graph into matchings such that the union of any two matchings is a Hamiltonian cycle. Each pan‐Hamiltonian Latin square of order n describes a perfect 1‐factorization of K_n,n, and vice versa. Perfect 1‐factorizations of K_n,n can be constructed from a perfect 1‐factorization of K_n+1. Six of the seven main classes of atomic squares of order 11 can be obtained in this way. For each atomic square of order 11, we find the largest set of Mutually Orthogonal Latin Squares (MOLS) involving that square. We discuss algorithms for counting orthogonal mates, and discover the number of orthogonal mates possessed by the cyclic squares of orders up to 11 and by Parker's famous turn‐square. We find that the number of atomic orthogonal mates possessed by a Latin square is not a main class invariant. We also define a new sort of Latin square, called a pairing square, which is mapped to its transpose by an involution acting on the symbols. We show that pairing squares are often orthogonal mates for symmetric Latin squares. Finally, we discover connections between our atomic squares and Franklin's diagonally cyclic self‐orthogonal squares, and we correct a theorem of Longyear which uses tactical representations to identify self‐orthogonal Latin squares in the same main class as a given Latin square. © 2003 Wiley Periodicals, Inc.     

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.     

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.     

Vertex disjoint equivalent subgraphs of order 3

Let k be a fixed integer at least 3. It is proved that every graph of order (2k ? 1 ? 1/k)n + O(1) contains n vertex disjoint induced subgraphs of order k such that these subgraphs are equivalent to each other and they are equivalent to one of four graphs: a clique, an independent set, a star, or the complement of a star. In particular, by substituting 3 for k, it is proved that every graph of order 14n/3 + O(1) contains n vertex disjoint induced subgraphs of order 3 such that they are equivalent to each other. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 159–166, 2007     

Subdivisions of large complete bipartite graphs and long induced paths in k‐connected graphs

It is proved that for every positive integers k, r and s there exists an integer n = n(k,r,s) such that every k‐connected graph of order at least n contains either an induced path of length s or a subdivision of the complete bipartite graph K_k,r. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 270–274, 2004