Critical sets in back circulant latin squares

Summary To date very few families of critical sets for latin squares are known. In this paper a new family of critical sets for back circulant latin squares is identified. The proof that each element of the critical set is an essential part of the reconstruction process relies on the proof of the existence of a large number of latin interchanges.     

On the existence of nested orthogonal arrays

A nested orthogonal array is an OA(N,k,s,g) which contains an OA(M,k,r,g) as a subarray. Here r<s and M<N. Necessary conditions for the existence of such arrays are obtained in the form of upper bounds on k, given N, M, s, r and g. Examples are given to show that these bounds are quite powerful in proving nonexistence. The link with incomplete orthogonal arrays is also indicated.     

On the Number of Latin Squares

We (1) determine the number of Latin rectangles with 11 columns and each possible number of rows, including the Latin squares of order 11, (2) answer some questions of Alter by showing that the number of reduced Latin squares of order n is divisible by f! where f is a particular integer close to (3) provide a formula for the number of Latin squares in terms of permanents of (+1, −1)-matrices, (4) find the extremal values for the number of 1-factorisations of k-regular bipartite graphs on 2n vertices whenever 1 ≤ k ≤ n ≤ 11, (5) show that the proportion of Latin squares with a non-trivial symmetry group tends quickly to zero as the order increases. Received September 3, 2004     

An even side analogue of Room squares

A Room square of even side cannot exist. We study arrays of even side which very closely resemble Room squares. The spectrum is determined: the desired arrays exist for all even sides exceeding 4. These arrays are useful in a construction for Room squares containing subsquares. It is shown that, for alln4, and all oddr7 (exceptr=11), there is a Room square of sidenr +n – 1 which contains subsquares of sidesr and 2n – 1.     

Colouring games based on autotopisms of Latin hyper-rectangles

Abstract

Every partial colouring of a Hamming graph is uniquely related to a partial Latin hyper-rectangle. In this paper we introduce the Θ-stabilized (a, b)-colouring game for Hamming graphs, a variant of the (a, b)-colouring game so that each move must respect a given autotopism Θ of the resulting partial Latin hyperrectangle. We examine the complexity of this variant by means of its chromatic number. We focus in particular on the bi-dimensional case, for which the game is played on the Cartesian product of two complete graphs, and also on the hypercube case.     

A tripling construction for mutually orthogonal symmetric hamiltonian double Latin squares

We provide two new constructions for pairs of mutually orthogonal symmetric hamiltonian double Latin squares. The first is a tripling construction, and the second is derived from known constructions of hamilton cycle decompositions of when is prime.     

Latin squares with pairwise orthogonal conjugates

Let L¹ denote the set of integers n such that there exists an idempotent Latin square of order n with all of its conjugates distinct and pairwise orthogonal. It is known that L¹ contains all sufficiently large integers. That is, there is a smallest integer n_o such that L¹ contains all integers greater than n_o. However, no upper bound for n_o has been given and the term “sufficiently large” is unspecified. The main purpose of this paper is to establish a concrete upper bound for n_o. In particular it is shown that L¹ contain all integers n>5594, with the possible exception of n=6810.     

A basic class of symmetric orthogonal functions with six free parameters

In a previous paper, we introduced a basic class of symmetric orthogonal functions (BCSOF) by an extended theorem for Sturm-Liouville problems with symmetric solutions. We showed that the foresaid class satisfies the differential equation

     

More orthogonal double covers of complete graphs by Hamiltonian paths

An orthogonal double cover (ODC) of the complete graph K_n by a graph G is a collection G of n spanning subgraphs of K_n, all isomorphic to G, such that any two members of G share exactly one edge and every edge of K_n is contained in exactly two members of G. In the 1980s Hering posed the problem to decide the existence of an ODC for the case that G is an almost-Hamiltonian cycle, i.e. a cycle of length n-1. It is known that the existence of an ODC of K_n by a Hamiltonian path implies the existence of ODCs of K_4n and of K_16n, respectively, by almost-Hamiltonian cycles. Horton and Nonay introduced two-colorable ODCs and showed: If there are an ODC of K_n by a Hamiltonian path for some n?3 and a two-colorable ODC of K_q by a Hamiltonian path for some prime power q?5, then there is an ODC of K_qn by a Hamiltonian path. In [U. Leck, A class of 2-colorable orthogonal double covers of complete graphs by hamiltonian paths, Graphs Combin. 18 (2002) 155-167], two-colorable ODCs of K_n and K_2n, respectively, by Hamiltonian paths were constructed for all odd square numbers n?9. Here we continue this work and construct cyclic two-colorable ODCs of K_n and K_2n, respectively, by Hamiltonian paths for all n of the form n=4k²+1 or n=(k²+1)/2 for some integer k.     

Some new conjugate orthogonal Latin squares

We present some new conjugate orthogonal Latin squares which are obtained from a direct method of construction of the starter-adder type. Combining these new constructions with earlier results of K. T. Phelps and the first author, it is shown that a (3, 2, 1)- (or (1, 3, 2)-) conjugate orthogonal Latin square of order v exists for all positive integers v ≠ 2, 6. It is also shown that a (3, 2, 1)- (or (1, 3, 2)-) conjugate orthogonal idempotent Latin square of order v exists for all positive integers v ≠ 2, 3, 6 with one possible exception v = 12, and this result can be used to enlarge the spectrum of a certain class of Mendelsohn designs and provide better results for problems on embedding.     

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.     

一类强对称自正交对角数独的存在性

研究了强对称自正交对角数独,引申了Lorch的构造方法,利用有限域上的线性空间理论给出了基本构造,证明了:对所有奇素数p,存在一个p2阶强对称自正交对角数独.     

Nowhere-Zero 4-Flows,Simultaneous Edge-Colorings,And Critical Partial Latin Squares

It is proved in this paper that every bipartite graphic sequence with the minimum degree 2 has a realization that admits a nowhere-zero 4-flow. This result implies a conjecture originally proposed by Keedwell (1993) and reproposed by Cameron (1999) about simultaneous edge-colorings and critical partial Latin squares.* Partially supported by RGC grant HKU7054/03P. Partially supported by the National Security Agency under Grants MDA904-00-1-00614 and MDA904-01-1-0022.     

Balanced diagonals in frequency squares

We say that a diagonal in an array is $\lambda$-balanced if each entry occurs $\lambda$ times. Let $L$ be a frequency square of type $F(n;\lambda )$; that is, an $n\times n$ array in which each entry from $\{1,2,\dots ,m=n∕\lambda \}$ occurs $\lambda$ times per row and $\lambda$ times per column. We show that if $m?3$, $L$ contains a $\lambda$-balanced diagonal, with only one exception up to equivalence when $m=2$. We give partial results for $m?4$ and suggest a generalization of Ryser’s conjecture, that every Latin square of odd order has a transversal. Our method relies on first identifying a small substructure with the frequency square that facilitates the task of locating a balanced diagonal in the entire array.     

On the 0-1 matrices whose squares are 0-1 matrices

We study the 0-1 matrices whose squares are still 0-1 matrices and determine the maximal number of ones in such a matrix. The maximizing matrices are also specified. This solves a special case of a problem posed by Zhan.     

Existence of conjugate orthogonal diagonal Latin squares

We shall refer to a diagonal Latin square which is orthogonal to its (3, 2, 1)-conjugate and having its (3, 2, 1)-conjugate also a diagonal Latin square as a (3, 2, 1)-conjugate orthogonal diagonal Latin square, briefly CODLS. This article investigates the spectrum of CODLS and it is found that it contains all positive integers v except 2, 3, 6, and possibly 10. © 1997 John Wiley & Sons, Inc. J Combin Designs 5: 449–461, 1997