On orthogonal generalized equitable rectangles

In this note, we give a complete solution of the existence of orthogonal generalized equitable rectangles, which was raised as an open problem in by Stinson (Des Codes Cryptogr 45:347–357, 2007).      

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

Existence of centre-complementary magic rectangles

A magic rectangle of size $(m_1,m_2)$ is an $m_1\times m_2$ array consisting of $m_1{m}_2$ consecutive integers in which the sum of each row is a constant and the sum of each column is another (different if $m_1\ne m_2$). It is centre-complementary if the sum of any pair of centrally symmetric positions is constant. As a natural generalization of symmetric magic squares, centre-complementary magic rectangles are instrumental in the construction of 3-dimensional rectangles. In this paper, we focus our attention on the existence of centre-complementary magic rectangles and prove that the necessary conditions for the existence of centre-complementary magic rectangles are also sufficient.     

Triples of orthogonal Latin and Youden rectangles for small orders

We have performed a complete enumeration of nonisotopic triples of mutually orthogonal Latin rectangles for . Here we will present a census of such triples, classified by various properties, including the order of the autotopism group of the triple. As part of this, we have also achieved the first enumeration of pairwise orthogonal triples of Youden rectangles. We have also studied orthogonal triples of rectangles which are formed by extending mutually orthogonal triples with nontrivial autotopisms one row at a time, and requiring that the autotopism group is nontrivial in each step. This class includes a triple coming from the projective plane of order 8. Here we find a remarkably symmetrical pair of triples of rectangles, formed by juxtaposing two selected copies of complete sets of mutually orthogonal Latin squares of order 4.     

两两正交拉丁方最大数目的新上界

记D（x）是使得TD（x，n）存在的最小的数．本文给出D（x）的一个上界．     

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.     

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.     

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

Direct Constructions for General Families of Cyclic Mutually Nearly Orthogonal Latin Squares

Two Latin squares and , of even order n with entries , are said to be nearly orthogonal if the superimposition of L on M yields an array in which each ordered pair , and , occurs at least once and the ordered pair occurs exactly twice. In this paper, we present direct constructions for the existence of general families of three cyclic mutually orthogonal Latin squares of orders , , and . The techniques employed are based on the principle of Methods of Differences and so we also establish infinite classes of “quasi‐difference” sets for these orders.     

Latin trades on three or four rows

Latin trades are closely related to the problem of critical sets in Latin squares. We denote the cardinality of the smallest critical set in any Latin square of order n by scs(n). A consideration of Latin trades which consist of just two columns, two rows, or two elements establishes that scs(n)?n-1. We conjecture that a consideration of Latin trades on four rows may establish that scs(n)?2n-4. We look at various attempts to prove a conjecture of Cavenagh about such trades. The conjecture is proven computationally for values of n less than or equal to 9. In particular, we look at Latin squares based on the group table of Z_n for small n and trades in three consecutive rows of such Latin squares.     

Completing Latin squares: Critical sets II

It is shown that each critical set in a Latin square of order n > 6 has to have at least empty cells. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 77–83, 2007     

正交拉丁方组和泛对角线幻方的一种构造法

利用线性取余变换构造素数阶完备正交拉丁方组,给出泛对角线幻方的一种构造法.     

On the distance between distinct group Latin squares

In an article in 1992, Drápal addressed the question of how far apart the multiplication tables of two groups can be? In this article we continue this investigation; in particular, we study the interaction between partial equalities in the multiplication tables of the two groups and their subgroup structure. © 1997 John Wiley & Sons, Inc. J Combin Designs 5: 235–248, 1997     

On the threshold problem for Latin boxes

Let m ≤ n ≤ k. An m × n × k 0‐1 array is a Latin box if it contains exactly m n ones, and has at most one 1 in each line. As a special case, Latin boxes in which m = n = k are equivalent to Latin squares. Let be the distribution on m × n × k 0‐1 arrays where each entry is 1 with probability p, independently of the other entries. The threshold question for Latin squares asks when contains a Latin square with high probability. More generally, when does support a Latin box with high probability? Let ε > 0. We give an asymptotically tight answer to this question in the special cases where n = k and , and where n = m and . In both cases, the threshold probability is . This implies threshold results for Latin rectangles and proper edge‐colorings of K_n,n.     

On the orthogonal Latin squares polytope

Since 1782, when Euler addressed the question of existence of a pair of orthogonal Latin squares (OLS) by stating his famous conjecture, these structures have remained an active area of research. In this paper, we examine the polyhedral aspects of OLS. In particular, we establish the dimension of the OLS polytope, describe all cliques of the underlying intersection graph and categorize them into three classes. Two of these classes are shown to induce facet-defining inequalities of Chvátal rank two. For each such class, we provide a polynomial separation algorithm of the lowest possible complexity.     

Random Latin square graphs

In this paper we introduce new models of random graphs, arising from Latin squares which include random Cayley graphs as a special case. We investigate some properties of these graphs including their clique, independence and chromatic numbers, their expansion properties as well as their connectivity and Hamiltonicity. The results obtained are compared with other models of random graphs and several similarities and differences are pointed out. For many properties our results for the general case are as strong as the known results for random Cayley graphs and sometimes improve the previously best results for the Cayley case. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Recursive construction of non-cyclic pandiagonal Latin squares

The pandiagonal Latin squares constructed using Hedayat’s method are cyclic. During the last decades several authors have described methods for constructing pandiagonal Latin squares which are semi-cyclic. In this paper we propose a recursive method for constructing non-cyclic pandiagonal Latin squares of any given order n$n$, where n$n$ is a positive composite integer not divisible by 2 or 3. We also investigate the orthogonality properties of the constructed squares and extend our method to construct non-cyclic pandiagonal Sudoku.