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.     

On functional specification of latin squares

This paper studies functional methods for specification of Latin squares over the sets of n-dimensional Boolean vectors, n-dimensional vectors over an arbitrary finite prime field and over an arbitrary finite Abelian group. In conclusion, a method for constructing classes of nongroup Latin squares is presented.     

Constructing orthogonal pandiagonal Latin squares and panmagic squares from modular n‐queens solutions

In this article, we show how to construct pairs of orthogonal pandiagonal Latin squares and panmagic squares from certain types of modular n‐queens solutions. We prove that when these modular n‐queens solutions are symmetric, the panmagic squares thus constructed will be associative, where for an n × n associative magic square A = (a_ij), for all i and j it holds that a_ij + an?i?1,n?j?1 = c for a fixed c. We further show how to construct orthogonal Latin squares whose modular difference diagonals are Latin from any modular n‐queens solution. As well, we analyze constructing orthogonal pandiagonal Latin squares from particular classes of non‐linear modular n‐queens solutions. These pandiagonal Latin squares are not row cyclic, giving a partial solution to a problem of Hedayat. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 221–234, 2007     

An expression for the number of equivalence classes of Latin squares under row and column permutations

In this paper equivalence classes of Latin squares induced by row and column permutations are considered. An expression for the number of such classes for an nth order Latin square is obtained in terms of Latin rectangles with n rows. In the case where n is prime the expression gives a simple result for those squares invariant under a permutation other than the identity.     

Latin squares with one subsquare

We look at two classes of constructions for Latin squares which have exactly one proper subsquare. The first class includes known squares due to McLeish and to Kotzig and Turgeon, which had not previously been shown to possess unique subsquares. The second class is a new construction called the corrupted product. It uses subsquare‐free squares of orders m and n to build a Latin square of order mn whose only subsquare is one of the two initial squares. We also provide tight bounds on the size of a unique subsquare and a survey of small order examples. Finally, we foreshadow how our squares might be used to create new Latin squares devoid of proper subsquares—so called N_∞ squares. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 128–146, 2001     

The Order of Automorphisms of Quasigroups

We prove quadratic upper bounds on the order of any autotopism of a quasigroup or Latin square, and hence also on the order of any automorphism of a Steiner triple system or 1‐factorization of a complete graph. A corollary is that a permutation σ chosen uniformly at random from the symmetric group will almost surely not be an automorphism of a Steiner triple system of order n, a quasigroup of order n or a 1‐factorization of the complete graph . Nor will σ be one component of an autotopism for any Latin square of order n. For groups of order n it is known that automorphisms must have order less than n, but we show that quasigroups of order n can have automorphisms of order greater than n. The smallest such quasigroup has order 7034. We also show that quasigroups of prime order can possess autotopisms that consist of three permutations with different cycle structures. Our results answer three questions originally posed by D.  Stones.     

Generating uniformly distributed random latin squares

By simulating an ergodic Markov chain whose stationary distribution is uniform over the space of n × n Latin squares, we can obtain squares that are (approximately) uniformly distributed; we offer two such chains. The central issue is the construction of “moves” that connect the squares. Our first approach uses the fact that an n × n Latin square is equivalent to an n × n × n contingency table in which each line sum equals 1. We relax the nonnegativity condition on the table's cells, allowing “improper” tables that have a single—1-cell. A simple set of moves connects this expanded space of tables [the diameter of the associated graph is bounded by 2(n − 1)³], and suggests a Markov chain whose subchain of proper tables has the desired uniform stationary distribution (with an average of approximately n steps between proper tables). By grouping these moves appropriately, we derive a class of moves that stay within the space of proper Latin squares [with graph diameter bounded by 4(n − 1)²]; these may also be used to form a suitable Markov chain. © 1996 John Wiley & Sons, Inc.     

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.     

The number of transversals in a Latin square

A Latin Square of order n is an n × n array of n symbols, in which each symbol occurs exactly once in each row and column. A transversal is a set of n entries, one selected from each row and each column of a Latin Square of order n such that no two entries contain the same symbol. Define T(n) to be the maximum number of transversals over all Latin squares of order n. We show that for n ≥ 5, where b ≈ 1.719 and c ≈ 0.614. A corollary of this result is an upper bound on the number of placements of n non-attacking queens on an n × n toroidal chess board. Some divisibility properties of the number of transversals in Latin squares based on finite groups are established. We also provide data from a computer enumeration of transversals in all Latin Squares of order at most 9, all groups of order at most 23 and all possible turn-squares of order 14.     

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.     

Cycle structure of autotopisms of quasigroups and latin squares

An autotopism of a Latin square is a triple (α, β, γ) of permutations such that the Latin square is mapped to itself by permuting its rows by α, columns by β, and symbols by γ. Let Atp(n) be the set of all autotopisms of Latin squares of order n. Whether a triple (α, β, γ) of permutations belongs to Atp(n) depends only on the cycle structures of α, β, and γ. We establish a number of necessary conditions for (α, β, γ) to be in Atp(n), and use them to determine Atp(n) for n?17. For general n, we determine if (α, α, α)∈Atp(n) (that is, if αis an automorphism of some quasigroup of order n), provided that either αhas at most three cycles other than fixed points or that the non‐fixed points of α are in cycles of the same length. © 2011 Wiley Periodicals, Inc. J Combin Designs     

New negative Latin square type partial difference sets in nonelementary abelian 2-groups and 3-groups

A partial difference set having parameters (n ², r(n − 1), n + r ² − 3r, r ² − r) is called a Latin square type partial difference set, while a partial difference set having parameters (n ², r(n + 1), − n + r ² + 3r, r ² + r) is called a negative Latin square type partial difference set. Nearly all known constructions of negative Latin square partial difference sets are in elementary abelian groups. In this paper, we develop three product theorems that construct negative Latin square type partial difference sets and Latin square type partial difference sets in direct products of abelian groups G and G′ when these groups have certain Latin square or negative Latin square type partial difference sets. Using these product theorems, we can construct negative Latin square type partial difference sets in groups of the form where the s _i are nonnegative integers and s ₀ + s ₁ ≥ 1. Another significant corollary to these theorems are constructions of two infinite families of negative Latin square type partial difference sets in 3-groups of the form for nonnegative integers s _i . Several constructions of Latin square type PDSs are also given in p-groups for all primes p. We will then briefly indicate how some of these results relate to amorphic association schemes. In particular, we construct amorphic association schemes with 4 classes using negative Latin square type graphs in many nonelementary abelian 2-groups; we also use negative Latin square type graphs whose underlying sets can be elementary abelian 3-groups or nonelementary abelian 3-groups to form 3-class amorphic association schemes.      

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     

Negative Latin square type partial difference sets and amorphic association schemes with Galois rings

A partial difference set (PDS) having parameters (n², r(n?1), n+r²?3r, r²?r) is called a Latin square type PDS, while a PDS having parameters (n², r(n+1), ?n+r²+3r, r² +r) is called a negative Latin square type PDS. There are relatively few known constructions of negative Latin square type PDSs, and nearly all of these are in elementary abelian groups. We show that there are three different groups of order 256 that have all possible negative Latin square type parameters. We then give generalized constructions of negative Latin square type PDSs in 2‐groups. We conclude by discussing how these results fit into the context of amorphic association schemes and by stating some open problems. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 266‐282, 2009     

Embedding a Latin square with transversal into a projective space

A Latin square of side n defines in a natural way a finite geometry on 3n points, with three lines of size n and n² lines of size 3. A Latin square of side n with a transversal similarly defines a finite geometry on 3n+1 points, with three lines of size n, n²−n lines of size 3, and n concurrent lines of size 4. A collection of k mutually orthogonal Latin squares defines a geometry on kn points, with k lines of size n and n² lines of size k. Extending the work of Bruen and Colbourn [A.A. Bruen, C.J. Colbourn, Transversal designs in classical planes and spaces, J. Combin. Theory Ser. A 92 (2000) 88-94], we characterise embeddings of these finite geometries into projective spaces over skew fields.     

Near‐automorphisms of Latin squares

We define a near‐automorphism α of a Latin square L to be an isomorphism such that L and α L differ only within a 2 × 2 subsquare. We prove that for all n≥2 except n∈{3, 4}, there exists a Latin square which exhibits a near‐automorphism. We also show that if α has the cycle structure (2, n ? 2), then L exists if and only if n≡2 (mod 4), and can be constructed from a special type of partial orthomorphism. Along the way, we generalize a theorem by Marshall Hall, which states that any Latin rectangle can be extended to a Latin square. We also show that if α has at least 2 fixed points, then L must contain two disjoint non‐trivial subsquares. Copyright © 2011 John Wiley & Sons, Ltd. 19:365‐377, 2011     

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.     

Generalized latin square

LetX be a n-set and letA = [a_ij] be an xn matrix for whichaij ?X, for 1 ≤i, j ≤n. A is called a generalized Latin square onX, if the following conditions is satisfied: $ \cup _{i = 1}^n a_{ij} = X = \cup _{j = 1}^n a_{ij} $ . In this paper, we prove that every generalized Latin square has an orthogonal mate and introduce a H_v -structure on a set of generalized Latin squares. Finally, we prove that every generalized Latin square of ordern, has a transversal set.     

Existence of weakly pandiagonal orthogonal Latin squares

A weakly pandiagonal Latin square of order n over the number set {0, 1, . . . , n-1} is a Latin square having the property that the sum of the n numbers in each of 2n diagonals is the same. In this paper, we shall prove that a pair of orthogonal weakly pandiagonal Latin squares of order n exists if and only if n ≡ 0, 1, 3 (mod 4) and n≠3.     

Latin squares and superqueens

Let L be a Latin square of order n with entries from {0, 1,…, n ? 1}. In addition, L is said to have the (n, k) property if, in each right or left wrap around diagonal, the number of cells with entries smaller than k is exactly k. It is established that a necessary and sufficient condition for the existence of Latin squares having the (n, k) property is that of (2|n ? 2| k) and (3|n ? 3| k). Also, these Latin squares are related to a problem of placing nonattacking queens on a toroidal chessboard.