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.     

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     

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.     

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

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

New quasi-symmetric designs constructed using mutually orthogonal Latin squares and Hadamard matrices

Using Hadamard matrices and mutually orthogonal Latin squares, we construct two new quasi-symmetric designs, with parameters 2 − (66,30,29) and 2 − (78,36,30). These are the first examples of quasi-symmetric designs with these parameters. The parameters belong to the families 2 − (2u ² − u,u ² − u,u ² − u − 1) and 2 − (2u ² + u,u ²,u ² − u), which are related to Hadamard parameters. The designs correspond to new codes meeting the Grey–Rankin bound.     

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.     

An LP-based proof for the non-existence of a pair of orthogonal Latin squares of order 6

This paper presents an alternative proof for the non-existence of orthogonal Latin squares of order 6. Our method is algebraic, rather than enumerative, and applies linear programming in order to obtain appropriate dual vectors. The proof is achievable only after extending previously known results for symmetry elimination.     

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.     

Coloring graphs from lists with bounded size of their union

A graph G is k‐choosable if its vertices can be colored from any lists L(ν) of colors with |L(ν)| ≥ k for all ν ∈ V(G). A graph G is said to be (k,?)‐choosable if its vertices can be colored from any lists L(ν) with |L(ν)| ≥k, for all ν∈ V(G), and with . For each 3 ≤ k ≤ ?, we construct a graph G that is (k,?)‐choosable but not (k,? + 1)‐choosable. On the other hand, it is proven that each (k,2k ? 1)‐choosable graph G is O(k · ln k · 2^4k)‐choosable. © 2005 Wiley Periodicals, Inc. J Graph Theory     

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.     

Large sets of disjoint group‐divisible designs with block size three and type 2n41

Large sets of disjoint group‐divisible designs with block size three and type 2ⁿ4¹ have been studied by Schellenberg, Chen, Lindner and Stinson. These large sets have applications in cryptography in the construction of perfect threshold schemes. It is known that such large sets can exist only for n ≡ 0 (mod 3) and do exist for n = 6 and for all n = 3^k, k ≥ 1. In this paper, we present new recursive constructions and use them to show that such large sets exist for all odd n ≡ 0 (mod 3) and for even n = 24m, where m odd ≥ 1. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 285–296, 2001     

Sum of squares method for sensor network localization

We formulate the sensor network localization problem as finding the global minimizer of a quartic polynomial. Then sum of squares (SOS) relaxations can be applied to solve it. However, the general SOS relaxations are too expensive to implement for large problems. Exploiting the special features of this polynomial, we propose a new structured SOS relaxation, and discuss its various properties. When distances are given exactly, this SOS relaxation often returns true sensor locations. At each step of interior point methods solving this SOS relaxation, the complexity is , where n is the number of sensors. When the distances have small perturbations, we show that the sensor locations given by this SOS relaxation are accurate within a constant factor of the perturbation error under some technical assumptions. The performance of this SOS relaxation is tested on some randomly generated problems.     

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.     

A new class of Latin hypercube designs with high-dimensional hidden projective uniformity

Latin hypercube design is a good choice for computer experiments. In this paper, we construct a new class of Latin hypercube designs with some high-dimensional hidden projective uniformity. The construction is based on a new class of orthogonal arrays of strength two which contain higher strength orthogonal arrays after their levels are collapsed. As a result, the obtained Latin hypercube designs achieve higher-dimensional uniformity when projected onto the columns corresponding to higher strength orthogonal arrays, as well as twodimensional projective uniformity. Simulation study shows that the constructed Latin hypercube designs are significantly superior to the currently used designs in terms of the times of correctly identifying the significant effects.