On the range of influences in back-circulant Latin squares

In this note we obtain a large lower bound for the index of a certain critical set in the back-circulant Latin squares of odd order. This resolves in the negative a conjecture of Fitina, Seberry and Chaudhry [Back-circulant Latin square and the influence of a set, Austral. J. Combin. 20 (1999) 163-180].     

Smallest defining sets of directed triple systems

A directed triple system of order v, , is a pair (V,B) where V is a set of v elements and B is a collection of ordered triples of distinct elements of V with the property that every ordered pair of distinct elements of V occurs in exactly one triple as a subsequence. A set of triples in a D is a defining set for D if it occurs in no other on the same set of points. A defining set for D is a smallest defining set for D if D has no defining set of smaller cardinality. In this paper we are interested in the quantity

     

A graph-theoretic proof of the non-existence of self-orthogonal Latin squares of order 6

The non-existence of a pair of mutually orthogonal Latin squares of order six is a well-known result in the theory of combinatorial designs. It was conjectured by Euler in 1782 and was first proved by Tarry in 1900 by means of an exhaustive enumeration of equivalence classes of Latin squares of order six. Various further proofs have since been given, but these proofs generally require extensive prior subject knowledge in order to follow them, or are ‘blind’ proofs in the sense that most of the work is done by computer or by exhaustive enumeration. In this paper we present a graph-theoretic proof of a somewhat weaker result, namely the non-existence of self-orthogonal Latin squares of order six, by introducing the concept of a self-orthogonal Latin square graph. The advantage of this proof is that it is easily verifiable and accessible to discrete mathematicians not intimately familiar with the theory of combinatorial designs. The proof also does not require any significant prior knowledge of graph theory.     

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.      

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.     

Quarter-regular biembeddings of Latin squares

We apply a recursive construction for biembeddings of Latin squares to produce a new infinite family of biembeddings of cyclic Latin squares of even side having a high degree of symmetry. Reapplication of the construction yields two further classes of biembeddings.     

The fine structures of three symmetric Latin squares with even orders

Denote by SFin(v) the set of all integer pairs (t, s) for which there exist three symmetric Latin squares of order v on the same set having fine structure (t, s). We completely determine the set SFin(2n) for any integer n ≥ 5.     

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.     

Large sets of resolvable idempotent Latin squares

An idempotent Latin square of order v is called resolvable and denoted by RILS(v) if the v(v−1) off-diagonal cells can be resolved into v−1 disjoint transversals. A large set of resolvable idempotent Latin squares of order v, briefly LRILS(v), is a collection of v−2 RILS(v)s pairwise agreeing on only the main diagonal. In this paper we display some recursive and direct constructions for LRILSs.     

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

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

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.     

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.     

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.     

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.     

Groupoids with quasigroup and Latin square properties

Connections of some groupoid identities with the quasigroup and Latin square properties are investigated using combinatorial methods.     

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

Generalized Latin squares on the torus

The notion of a Latin square is generalized. The natural object on which to define this extension is the torus. A theorem is proved which shows that the existence of a Latin square implies the existence of a linear Latin square, a Latin square with special form. The theorems in the paper are used to provide alternate proofs of results due to Pólya and Chandra (in relation to a problem of Moser). The inability to extend the results to orthogonal Latin squares is noted.     

When is a partial Latin square uniquely completable, but not its completable product?

Let P and Q be uniquely completable partial Latin squares. It is an open problem to determine necessary and sufficient conditions so that the completable product P⊗Q is also uniquely completable. So far, only a few specific examples of P have been given such that the completable product of P with itself (P⊗P) does not have a unique completion. In this paper, we find a whole class of such partial Latin squares.