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

Completing Latin squares: Critical sets

It is shown that a critical set in a Latin square of order n≥8 has to have at least elements. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 419–432, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10028     

On the Distances between Latin Squares and the Smallest Defining Set Size

In this note, we show that for each Latin square L of order , there exists a Latin square of order n such that L and differ in at most cells. Equivalently, each Latin square of order n contains a Latin trade of size at most . We also show that the size of the smallest defining set in a Latin square is .     

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     

The fine structures of three Latin squares

Denote by Fin(υ) the set of all integral pairs (t,s) for which there exist three Latin squares of order υ on the same set having fine structure (t,s). We determine the set Fin(υ) for any integer v ≥ 9. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 85–110, 2006     

Intercalates and discrepancy in random Latin squares

An intercalate in a Latin square is a 2 × 2 Latin subsquare. Let be the number of intercalates in a uniformly random n × n Latin square. We prove that asymptotically almost surely , and that (therefore asymptotically almost surely for any ). This significantly improves the previous best lower and upper bounds. We also give an upper tail bound for the number of intercalates in 2 fixed rows of a random Latin square. In addition, we discuss a problem of Linial and Luria on low‐discrepancy Latin squares.     

Orthogonal factor‐pair Latin squares of prime‐power order

We introduce a linear method for constructing factor‐pair Latin squares of prime‐power order and we identify criteria for determining whether two factor‐pair Latin squares constructed using this linear method are orthogonal. Then we show that families of pairwise mutually orthogonal diagonal factor‐pair Latin squares exist in all prime‐power orders.     

Negative Latin square type partial difference sets in nonabelian groups of order 64

There exist few examples of negative Latin square type partial difference sets (NLST PDSs) in nonabelian groups. We present a list of 176 inequivalent NLST PDSs in 48 nonisomorphic, nonabelian groups of order 64. These NLST PDSs form 8 nonisomorphic strongly regular graphs. These PDSs were constructed using a combination of theoretical techniques and computer search, both of which are described. The search was run exhaustively on 212/267 nonisomorphic groups of order 64.     

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.      

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     

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.     

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.     

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