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 .     

On the Hamilton–Waterloo Problem with Odd Orders

Given nonnegative integers , the Hamilton–Waterloo problem asks for a factorization of the complete graph into α ‐factors and β ‐factors. Without loss of generality, we may assume that . Clearly, v odd, , , and are necessary conditions. To date results have only been found for specific values of m and n. In this paper, we show that for any integers , these necessary conditions are sufficient when v is a multiple of and , except possibly when or 3. For the case where we show sufficiency when with some possible exceptions. We also show that when are odd integers, the lexicographic product of with the empty graph of order n has a factorization into α ‐factors and β ‐factors for every , , with some possible exceptions.     

Latin Squares with a Unique Intercalate

Suppose that and . We construct a Latin square of order n with the following properties:

• has no proper subsquares of order 3 or more .
• has exactly one intercalate (subsquare of order 2) .
• When the intercalate is replaced by the other possible subsquare on the same symbols, the resulting Latin square is in the same species as .

Hence generalizes the square that Sade famously found to complete Norton's enumeration of Latin squares of order 7. In particular, is what is known as a self‐switching Latin square and possesses a near‐autoparatopism.     

On the Existence of

Let there is an . For or , has been determined by Hanani, and for or , has been determined by the first author. In this paper, we investigate the case . A necessary condition for is . It is known that , and that there is an for all with a possible exception . We need to consider the case . It is proved that there is an for all with an exception and a possible exception , thereby, .     

Tight Heffter Arrays Exist for all Possible Values

A tight Heffter array is an matrix with nonzero entries from such that (i) the sum of the elements in each row and each column is 0, and (ii) no element from appears twice. We prove that exist if and only if both m and n are at least 3. If H has the property that all entries are integers of magnitude at most , every row and column sum is 0 over the integers, and H also satisfies ), we call H an integer Heffter array. We show integer Heffter arrays exist if and only if . Finally, an integer Heffter array is shiftable if each row and column contains the same number of positive and negative integers. We show that shiftable integer arrays exists exactly when both are even.     

A Generalization of the Hamilton–Waterloo Problem on Complete Equipartite Graphs

The Hamilton–Waterloo problem asks for which s and r the complete graph can be decomposed into s copies of a given 2‐factor F₁ and r copies of a given 2‐factor F₂ (and one copy of a 1‐factor if n is even). In this paper, we generalize the problem to complete equipartite graphs and show that can be decomposed into s copies of a 2‐factor consisting of cycles of length xzm; and r copies of a 2‐factor consisting of cycles of length yzm, whenever m is odd, , , and . We also give some more general constructions where the cycles in a given two factor may have different lengths. We use these constructions to find solutions to the Hamilton–Waterloo problem for complete graphs.     

On Flag‐Transitive Symmetric Designs of Affine Type

It is shown that, if is a nontrivial 2‐ symmetric design, with , admitting a flag‐transitive automorphism group G of affine type, then , p an odd prime, and G is a point‐primitive, block‐primitive subgroup of . Moreover, acts flag‐transitively, point‐primitively on , and is isomorphic to the development of a difference set whose parameters and structure are also provided.     

Uniform Semi‐Latin Squares and Their Schur‐Optimality

Let n and k be integers, with and . An semi‐Latin square S is an array, whose entries are k‐subsets of an ‐set, the set of symbols of S, such that each symbol of S is in exactly one entry in each row and exactly one entry in each column of S. Semi‐Latin squares form an interesting class of combinatorial objects which are useful in the design of comparative experiments. We say that an semi‐Latin square S is uniform if there is a constant μ such that any two entries of S, not in the same row or column, intersect in exactly μ symbols (in which case ). We prove that a uniform semi‐Latin square is Schur‐optimal in the class of semi‐Latin squares, and so is optimal (for use as an experimental design) with respect to a very wide range of statistical optimality criteria. We give a simple construction to make an semi‐Latin square S from a transitive permutation group G of degree n and order , and show how certain properties of S can be determined from permutation group properties of G. If G is 2‐transitive then S is uniform, and this provides us with Schur‐optimal semi‐Latin squares for many values of n and k for which optimal semi‐Latin squares were previously unknown for any optimality criterion. The existence of a uniform semi‐Latin square for all integers is shown to be equivalent to the existence of mutually orthogonal Latin squares (MOLS) of order n. Although there are not even two MOLS of order 6, we construct uniform, and hence Schur‐optimal, semi‐Latin squares for all integers . & 2012 Wiley Periodicals, Inc. J. Combin. Designs 00: 1–13, 2012     

Skew Hadamard Difference Sets from Dickson Polynomials of Order 7

Skew Hadamard difference sets have been an interesting topic of study for over 70 years. For a long time, it had been conjectured the classical Paley difference sets (the set of nonzero quadratic residues in where ) were the only example in Abelian groups. In 2006, the first author and Yuan disproved this conjecture by showing that the image set of is a new skew Hadamard difference set in with m odd, where denotes the first kind of Dickson polynomials of order n and . The key observation in the proof is that is a planar function from to for m odd. Since then a few families of new skew Hadamard difference sets have been discovered. In this paper, we prove that for all , the set is a skew Hadamard difference set in , where m is odd and . The proof is more complicated and different than that of Ding‐Yuan skew Hadamard difference sets since is not planar in . Furthermore, we show that such skew Hadamard difference sets are inequivalent to all existing ones for by comparing the triple intersection numbers.     

Block‐Transitive and Point‐Primitive 2‐ Designs with Sporadic Socle

The purpose of this paper is to classify all pairs , where is a nontrivial 2‐ design, and acts transitively on the set of blocks of and primitively on the set of points of with sporadic socle. We prove that there exists only one such pair : is the unique 2‐(176,8,2) design and , the Higman–Sims simple group.     

A Direct Construction of Nontransitive Dice Sets

In this paper, we give a direct construction for a set of dice realizing any given tournament T. The construction for a tournament with n vertices requires dice with n sides if n is odd, sides if n is divisible by 4, and sides if mod 4. This appears to be the most efficient general construction to date. Our construction relies only on a standard construction from graph theory.     

The Hamilton–Waterloo Problem for ‐Factors and ‐Factors

The Hamilton–Waterloo problem asks for a 2‐factorization of (for v odd) or minus a 1‐factor (for v even) into ‐factors and ‐factors. We completely solve the Hamilton–Waterloo problem in the case of C₃‐factors and ‐factors for .     

The Existence and Construction of (K5∖e)‐Designs of Orders 27, 135, 162, and 216

The problem of the existence of a decomposition of the complete graph into disjoint copies of has been solved for all admissible orders n, except for 27, 36, 54, 64, 72, 81, 90, 135, 144, 162, 216, and 234. In this paper, I eliminate 4 of these 12 unresolved orders. Let Γ be a ‐design. I show that divides 2^k3 for some and that . I construct ‐designs by prescribing as an automorphism group, and show that up to isomorphism there are exactly 24 ‐designs with as an automorphism group. Moreover, I show that the full automorphism group of each of these designs is indeed . Finally, the existence of ‐designs of orders 135, 162, and 216 follows immediately by the recursive constructions given by G. Ge and A. C. H. Ling, SIAM J Discrete Math 21(4) (2007), 851–864.     

Enumerating the Walecki‐Type Hamiltonian Cycle Systems

Let be the complete graph on v vertices. A Hamiltonian cycle system of odd order v (briefly ) is a set of Hamiltonian cycles of whose edges partition the edge set of . By means of a slight modification of the famous of Walecki, we obtain 2ⁿ pairwise distinct and we enumerate them up to isomorphism proving that this is equivalent to count the number of binary bracelets of length n, i.e. the orbits of , the dihedral group of order 2n, acting on binary n‐tuples.     

Decomposition of Complete Graphs into Isomorphic Complete Bipartite Graphs

A decomposition of a complete graph into disjoint copies of a complete bipartite graph is called a ‐design of order n. The existence problem of ‐designs has been completely solved for the graphs for , for , K_{2, 3} and K_{3, 3}. In this paper, I prove that for all , if there exists a ‐design of order N, then there exists a ‐design of order n for all (mod ) and . Giving necessary direct constructions, I provide an almost complete solution for the existence problem for complete bipartite graphs with fewer than 18 edges, leaving five orders in total unsolved.     

Optimal Two‐Dimensional Optical Orthogonal Codes with the Best Cross‐Correlation Constraint

The study of optical orthogonal codes has been motivated by an application in an optical code‐division multiple access system. From a practical point of view, compared to one‐dimensional optical orthogonal codes, two‐dimensional optical orthogonal codes tend to require smaller code length. On the other hand, in some circumstances only with good cross‐correlation one can deal with both synchronization and user identification. These motivate the study of two‐dimensional optical orthogonal codes with better cross‐correlation than auto‐correlation. This paper focuses on optimal two‐dimensional optical orthogonal codes with the auto‐correlation and the best cross‐correlation 1. By examining the structures of w‐cyclic group divisible designs and semi‐cyclic incomplete holey group divisible designs, we present new combinatorial constructions for two‐dimensional ‐optical orthogonal codes. When and , the exact number of codewords of an optimal two‐dimensional ‐optical orthogonal code is determined for any positive integers n and .     

Simple Signed Steiner Triple Systems

Let X be a v‐set, be a set of 3‐subsets (triples) of X, and be a partition of with . The pair is called a simple signed Steiner triple system, denoted by ST, if the number of occurrences of every 2‐subset of X in triples is one more than the number of occurrences in triples . In this paper, we prove that exists if and only if , , and , where and for , . © 2012 Wiley Periodicals, Inc. J. Combin. Designs 20: 332–343, 2012     

Detachments of Amalgamated 3‐Uniform Hypergraphs Factorization Consequences

A is a hypergraph obtained from by splitting some or all of its vertices into more than one vertex. Amalgamating a hypergraph can be thought of as taking , partitioning its vertices, then for each element of the partition squashing the vertices to form a single vertex in the amalgamated hypergraph . In this paper, we use Nash‐Williams lemma on laminar families to prove a detachment theorem for amalgamated 3‐uniform hypergraphs, which yields a substantial generalization of previous amalgamation theorems by Hilton, Rodger, and Nash‐Williams. To demonstrate the power of our detachment theorem, we show that the complete 3‐uniform n‐partite multihypergraph can be expressed as the union of k edge‐disjoint factors, where for , is ‐regular, if and only if:

1. for all ,
2. for each i, , and
3. .

     

Classification of Graeco‐Latin Cubes

A q‐ary code of length n, size M, and minimum distance d is called an code. An code with is said to be maximum distance separable (MDS). Here one‐error‐correcting () MDS codes are classified for small alphabets. In particular, it is shown that there are unique (5, 5³, 3)₅ and (5, 7³, 3)₇ codes and equivalence classes of (5, 8³, 3)₈ codes. The codes are equivalent to certain pairs of mutually orthogonal Latin cubes of order q, called Graeco‐Latin cubes.     

Asymptotic Size of Covering Arrays: An Application of Entropy Compression

A covering array is an array A such that each cell of A takes a value from a v‐set V, which is called the alphabet. Moreover, the set is contained in the set of rows of every subarray of A. The parameter N is called the size of an array and denotes the smallest N for which a exists. It is well known that  [10]. In this paper, we derive two upper bounds on using an algorithmic approach to the Lovász local lemma also known as entropy compression.