Search

In an earlier paper by three of the present authors and Csaba Schneider, it was shown that, for $$m\ge 2$$ m ≥ 2 , a set of $$m+1$$ m + 1 partitions of a set $$\Omega $$ Ω , any m of which are the minimal non-trivial elements of a Cartesian lattice, either form a Latin square (if $$m=2$$ m = 2 ), or generate a join-semilattice of dimension m associated with a diagonal group over a base group G. In this paper we investigate what happens if we have $$m+r$$ m + r partitions with $$r\ge 2$$ r ≥ 2 , any m of which are minimal elements of a Cartesian lattice. If $$m=2$$ m = 2 , this is just a set of mutually orthogonal Latin squares. We consider the case where all these squares are isotopic to Cayley tables of groups, and give an example to show the groups need not be all isomorphic. For $$m>2$$ m > 2 , things are more restricted. Any $$m+1$$ m + 1 of the partitions generate a join-semilattice admitting a diagonal group over a group G. It may be that the groups are all isomorphic, though we cannot prove this. Under an extra hypothesis, we show that G must be abelian and must have three fixed-point-free automorphisms whose product is the identity. (We describe explicitly all abelian groups having such automorphisms.) Under this hypothesis, the structure gives an orthogonal array, and conversely in some cases. If the group is cyclic of prime order p, then the structure corresponds exactly to an arc of cardinality $$m+r$$ m + r in the $$(m-1)$$ ( m - 1 ) -dimensional projective space over the field with p elements, so all known results about arcs are applicable. More generally, arcs over a finite field of order q give examples where G is the elementary abelian group of order q. These examples can be lifted to non-elementary abelian groups using p-adic techniques.

In this paper, I survey frame starters, as well as orthogonal and strong frame starters, in abelian groups. I mainly recall and re-examine existence and nonexistence results, but I will prove some new results as well.

A frequency $n$-cube $F^n(q;l_0,...,l_{m-1})$ is an $n$-dimensional $q$-by-...-by-$q$ array, where $q = l_0+...+l_{m-1}$, filled by numbers $0,...,m-1$ with the property that each line contains exactly $l_i$ cells with symbol $i$, $i = 0,...,m-1$ (a line consists of $q$ cells of the array differing in one coordinate). The trivial upper bound on the number of frequency $n$-cubes is $m^{(q-1)^{n}}$. We improve that lower bound for $n>2$, replacing $q-1$ by a smaller value, by constructing a testing set of size $s^{n}$, $s

Column replacement techniques for creating covering arrays rely on the construction of perfect and distributing hash families with few rows, having as many columns as possible for a specified number of symbols. To construct distributing hash families in which the number of rows is less than the strength, we examine a method due to Blackburn and extend it in three ways. First, the method is generalized from homogeneous hash families (in which every row has the same number of symbols) to heterogeneous ones. Second, the extension treats distributing hash families, in which only separation into a prescribed number of parts is required, rather than perfect hash families, in which columns must be completely separated. Third, the requirements on one of the main ingredients are relaxed to permit the use of a large class of distributing hash families, which we call fractal. Constructions for fractal perfect and distributing hash families are given, and applications to the construction of perfect hash families of large strength are developed., Comment: 21 pages, 0 figures

Statistical design of experiments is widely used in scientific and industrial investigations. A generalized minimum aberration (GMA) orthogonal array is optimum under the well-established, so-called GMA criterion, and such an array can extract as much information as possible at a fixed cost. Finding GMA arrays is an open (yet fundamental) problem in design of experiments because constructing such arrays becomes intractable as the number of runs and factors increase. We develop two directed enumeration algorithms that call the integer programming with isomorphism pruning algorithm of Margot (2007) for the purpose of finding GMA arrays. Our results include 16 GMA arrays that were not previously in the literature, along with documentation of the efficiencies that made the required calculations possible within a reasonable budget of computer time. We also validate heuristic algorithms against a GMA array catalog, by showing that they quickly output near GMA arrays, and then use the heuristics to find near GMA arrays when enumeration is computationally burdensome., Comment: 15 pages. arXiv admin note: text overlap with arXiv:1501.02281

A frequency square is a square matrix in which each row and column is a permutation of the same multiset of symbols. A frequency square is of type $$(n;\lambda )$$ if it contains $$n/\lambda $$ symbols, each of which occurs $$\lambda $$ times per row and $$\lambda $$ times per column. In the case when $$\lambda =n/2$$ we refer to the frequency square as binary. A set of k-MOFS $$(n;\lambda )$$ is a set of k frequency squares of type $$(n;\lambda )$$ such that when any two of the frequency squares are superimposed, each possible ordered pair occurs equally often. A set of k-maxMOFS $$(n;\lambda )$$ is a set of k-MOFS $$(n;\lambda )$$ that is not contained in any set of $$(k+1)$$ -MOFS $$(n;\lambda )$$ . For even n, let $$\mu (n)$$ be the smallest k such that there exists a set of k-maxMOFS(n; n/2). It was shown in Britz et al. (Electron. J. Combin. 27(3):#P3.7, 26 pp, 2020) that $$\mu (n)=1$$ if n/2 is odd and $$\mu (n)>1$$ if n/2 is even. Extending this result, we show that if n/2 is even, then $$\mu (n)>2$$ . Also, we show that whenever n is divisible by a particular function of k, there does not exist a set of $$k'$$ -maxMOFS(n; n/2) for any $$k'\leqslant k$$ . In particular, this means that $$\limsup \mu (n)$$ is unbounded. Nevertheless we can construct infinite families of maximal binary MOFS of fixed cardinality. More generally, let $$q=p^u$$ be a prime power and let $$p^v$$ be the highest power of p that divides n. If $$0\leqslant v-uh

It is known that N ( n ) , the maximum number of mutually orthogonal latin squares of order n, satisfies the lower bound N ( n ) ≥ n 1 / 14.8 for large n. For h ≥ 2 , relatively little is known about the quantity N ( h n ) , which denotes the maximum number of ‘HMOLS’ or mutually orthogonal latin squares having a common equipartition into n holes of a fixed size h. We generalize a difference matrix method that had been used previously for explicit constructions of HMOLS. An estimate of R.M. Wilson on higher cyclotomic numbers guarantees our construction succeeds in suitably large finite fields. Feeding this into a generalized product construction, we are able to establish the lower bound N ( h n ) ≥ ( log ⁡ n ) 1 / δ for any δ > 2 and all n > n 0 ( h , δ ) .

We show that for each reduced odd latin square of even order there exists at least one map such that its image is a reduced even latin square of the same order. We prove that this map is injective. As a consequence, we can show that the number of even latin squares of even order is bounded from below by the number of odd latin squares of the same order. This gives a positive answer to the Alon-Tarsi conjecture on even latin squares

A frequency $n$-cube $F^n(4;2,2)$ is an $n$-dimensional $4$-by-...-by-$4$ array filled by $0$s and $1$s such that each line contains exactly two $1$s. We classify the frequency $4$-cubes $F^4(4;2,2)$, find a testing set of size $25$ for $F^3(4;2,2)$, and derive an upper bound on the number of $F^n(4;2,2)$. Additionally, for any $n$ greater than $2$, we construct an $F^n(4;2,2)$ that cannot be refined to a latin hypercube, while each of its sub-$F^{n-1}(4;2,2)$ can. Keywords: frequency hypercube, frequency square, latin hypercube, testing set, MDS code, Comment: v.2: revised; computational data attached

We define a cover of a Latin square to be a set of entries that includes at least one representative of each row, column and symbol. A cover is minimal if it does not contain any smaller cover. A partial transversal is a set of entries that includes at most one representative of each row, column and symbol. A partial transversal is maximal if it is not contained in any larger partial transversal. We explore the relationship between covers and partial transversals. We prove the following: (1) The minimum size of a cover in a Latin square of order n is $$n+a$$ if and only if the maximum size of a partial transversal is either $$n-2a$$ or $$n-2a+1$$ . (2) A minimal cover in a Latin square of order n has size at most $$\mu _n=3(n+1/2-\sqrt{n+1/4})$$ . (3) There are infinitely many orders n for which there exists a Latin square having a minimal cover of every size from n to $$\mu _n$$ . (4) Every Latin square of order n has a minimal cover of a size which is asymptotically equal to $$\mu _n$$ . (5) If $$1\leqslant k\leqslant n/2$$ and $$n\geqslant 5$$ then there is a Latin square of order n with a maximal partial transversal of size $$n-k$$ . (6) For any $$\varepsilon >0$$ , asymptotically almost all Latin squares have no maximal partial transversal of size less than $$n-n^{2/3+\varepsilon }$$ .

A partial transversal T of a Latin square L is a set of entries of L in which each row, column and symbol is represented at most once. A partial transversal is maximal if it is not contained in a larger partial transversal. Any maximal partial transversal of a Latin square of order n has size at least ⌈ n 2 ⌉ and at most n. We say that a Latin square is omniversal if it possesses a maximal partial transversal of all plausible sizes and is near-omniversal if it possesses a maximal partial transversal of all plausible sizes except one. Evans (2019) showed that omniversal Latin squares of order n exist for any odd n ≠ 3 . By extending this result, we show that an omniversal Latin square of order n exists if and only if n ∉ { 3 , 4 } and n ≢ 2 ( mod 4 ) . Furthermore, we show that near-omniversal Latin squares exist for all orders n ≡ 2 ( mod 4 ) . Finally, we show that no non-trivial finite group has an omniversal Cayley table, and only 15 finite groups have a near-omniversal Cayley table. In fact, as n grows, Cayley tables of groups of order n miss a constant fraction of the plausible sizes of maximal partial transversals. In the course of proving this, we partially solve the following interesting problem in combinatorial group theory. Suppose that we have two finite subsets R , C ⊆ G of a group G such that | { r c : r ∈ R , c ∈ C } | = m . How large do | R | and | C | need to be (in terms of m) to be certain that R ⊆ x H and C ⊆ H y for some subgroup H of order m in G, and x , y ∈ G ?

An array is row-Latin if no symbol is repeated within any row. An array is Latin if it and its transpose are both row-Latin. A transversal in an $n\times n$ array is a selection of $n$ different symbols from different rows and different columns. We prove that every $n \times n$ Latin array containing at least $(2-\sqrt{2}) n^2$ distinct symbols has a transversal. Also, every $n \times n$ row-Latin array containing at least $\frac14(5-\sqrt{5})n^2$ distinct symbols has a transversal. Finally, we show by computation that every Latin array of order $7$ has a transversal, and we describe all smaller Latin arrays that have no transversal.

This paper deals with distinct computational methods to enumerate the set $\mathrm{PLR}(r,s,n;m)$ of $r \times s$ partial Latin rectangles on $n$ symbols with $m$ non-empty cells. For fixed $r$, $s$, and $n$, we prove that the size of this set is a symmetric polynomial of degree $3m$, and we determine the leading terms (the monomials of degree $3m$ through $3m-9$) using inclusion-exclusion. For $m \leq 13$, exact formulas for these symmetric polynomials are determined using a chromatic polynomial method. Adapting Sade's method for enumerating Latin squares, we compute the exact size of $\mathrm{PLR}(r,s,n;m)$, for all $r \leq s \leq n \leq 7$, and all $r \leq s \leq 6$ when $n=8$. Using an algebraic geometry method together with Burnside's Lemma, we enumerate isomorphism, isotopism, and main classes when $r \leq s \leq n \leq 6$. Numerical results have been cross-checked where possible., Comment: 36 pages, 2 figures, 15 tables

It is inevitable that the $L_{g}(s)$ association scheme with $g\geq 3, s\geq g+2$ is a pseudo-$L_{g}(s)$ association scheme. On the contrary, although $s^2$ treatments of the pseudo-$L_{g}(s)$ association scheme can form one $L_{g}(s)$ association scheme, it is not always an $L_{g}(s)$ association scheme. Mainly because the set of cardinality $s$, which contains two first-associates treatments of the pseudo-$L_{g}(s)$ association scheme, is non-unique. Whether the order $s$ of a Latin square $\mathbf{L}$ is a prime power or not, the paper proposes two new conditions in order to extend a $POL(s,w)$ containing $\mathbf{L}$. It has been known that a $POL(s,w)$ can be extended to a $POL(s,s-1)$ so long as Bruck's \cite{brh} condition $s\geq \frac{(s-1-w)^4-2(s-1-w)^3+2(s-1-w)^2+(s-1-w)}{2}$ is satisfied, Bruck's condition will be completely improved through utilizing six properties of the $L_{w+2}(s)$ association scheme in this paper. Several examples are given to elucidate the application of our results., Comment: 52 pages

Difference arrays are used in applications such as software testing, authentication codes and data compression. Pseudo-orthogonal Latin squares are used in experimental designs. A special class of pseudo-orthogonal Latin squares are the mutually nearly orthogonal Latin squares (MNOLS) first discussed in 2002, with general constructions given in 2007. In this paper we develop row complete MNOLS from difference covering arrays. We will use this connection to settle the spectrum question for sets of 3 mutually pseudo-orthogonal Latin squares of even order, for all but the order 146.

Strong orthogonal arrays were recently introduced and studied in He and Tang [Biometrika 100 (2013) 254–260] as a class of space-filling designs for computer experiments. To enjoy the benefits of better space-filling properties, when compared to ordinary orthogonal arrays, strong orthogonal arrays need to have strength three or higher, which may require run sizes that are too large for experimenters to afford. To address this problem, we introduce a new class of arrays, called strong orthogonal arrays of strength two plus. These arrays, while being more economical than strong orthogonal arrays of strength three, still enjoy the better two-dimensional space-filling property of the latter. Among the many results we have obtained on the characterizations and constructions of strong orthogonal arrays of strength two plus, worth special mention is their intimate connection with second-order saturated designs.

In this expository paper, we mainly study orthogonal arrays (OAs) of strength two having a row that is repeated $m$ times. It turns out that the Plackett-Burman bound (\cite{PB}) can be strengthened by a factor of $m$ for orthogonal arrays of strength two that contain a row that is repeated $m$ times. This is a consequence of a more general result due to Mukerjee, Qian and Wu \cite{Muk} that applies to orthogonal arrays of arbitrary strength $t$. We examine several proofs of the Plackett-Burman bound and discuss which of these proofs can be strengthened to yield the aforementioned bound for OAs of strength two with repeated rows. We also briefly discuss related bounds for $t$-designs, and OAs of strength $t$, when $t > 2$.

We construct sequencings for many groups that are a semi-direct product of an odd-order abelian group and a cyclic group of odd prime order. It follows from these constructions that there is a group-based complete Latin square of order $n$ if and only if $n \in \{ 1,2,4\}$ or there is a non-abelian group of order $n$., Comment: 12 pages

We construct orthogonal arrays OA λ ( k , n ) (of strength two) having a row that is repeated m times, where m is as large as possible. In particular, we consider OAs where the ratio m ∕ λ is as large as possible; these OAs are termed optimal. We provide constructions of optimal OAs for any k ≥ n + 1 , albeit with large λ . We also study basic OAs; these are optimal OAs in which gcd ( m , λ ) = 1 . We construct a basic OA with n = 2 and k = 4 t + 1 , provided that a Hadamard matrix of order 8 t + 4 exists. This completely solves the problem of constructing basic OAs with n = 2 , modulo the Hadamard matrix conjecture.

A $k$-plex in a latin square of order $n$ is a selection of $kn$ entries that includes $k$ representatives from each row and column and $k$ occurrences of each symbol. A $1$-plex is also known as a transversal.It is well known that if $n$ is even then $B_n$, the addition table for the integers modulo $n$, possesses no transversals. We show that there are a great many latin squares that are similar to $B_n$ and have no transversal. As a consequence, the number of species of transversal-free latin squares is shown to be at least $n^{n^{3/2}(1/2-o(1))}$ for even $n\rightarrow\infty$.We also produce various constructions for latin squares that have no transversal but do have a $k$-plex for some odd $k>1$. We prove a 2002 conjecture of the second author that for all even orders $n>4$ there is a latin square of order $n$ that contains a $3$-plex but no transversal. We also show that for odd $k$ and $m\geq 2$, there exists a latin square of order $2km$ with a $k$-plex but no $k'$-plex for odd $k'

We intend to solve Sudoku puzzles using various rules based on the structures and properties of the puzzle. In this paper, we shall present several structures related to either one potential solution or two potential solutions.

Several specific Franklin squares and magic squares are decomposed into their quotient and remainder squares. The results support the conjecture that Franklin used the Eulerian composition method to construct many of his squares. This method also can be used to construct new Franklin squares as illustrated herein., Comment: 15 pages, 4 figures

An algorithm that uses the cycle structure of the rows, or the columns, of a Latin square to compute its autotopy group is introduced. As a result, a bound for the size of the autotopy group is obtained. This bound is used to show that the computation time for the autotopy group of Latin squares that have two rows or two columns that map from one to the other by a permutation which decomposes into a bounded number of disjoint cycles, is polynomial in the order n .

Based on a previous generalization by the author of Latin squares to Latin boards, this paper generalizes partial Latin squares and related objects like partial Latin squares, completable partial Latin squares and Latin square puzzles. The latter challenge players to complete partial Latin squares, Sudoku being the most popular variant nowadays. The present generalization results in partial Latin boards, completable partial Latin boards and Latin puzzles. Provided examples of Latin puzzles illustrate how they differ from puzzles based on Latin squares. The examples include Sudoku Ripeto and Custom Sudoku, two new Sudoku variants. This is followed by a discussion of methods to find Latin boards and Latin puzzles amenable to being solved by human players, with an emphasis on those based on constraint programming. The paper also includes an analysis of objective and subjective ways to measure the difficulty of Latin puzzles., Comment: 41 pages, 31 figures

The sign of a Latin square is −1 if it has an odd number of rows and columns that are odd permutations; otherwise, it is +1. LetLEnandLonbe, respectively, the number of Latin squares of ordernwith sign +1 and −1. The Alon-Tarsi conjecture asserts thatLEn≠Lonwhennis even. Drisko showed thatLEp+1≢Lop+1(modp3) for primep≥ 3 and asked if similar congruences hold for orders of the formpk+ 1,p+ 3, orpq+ 1. In this article we show that ift≤n, thenLEn+1≢L0n+1(modt3) only ift = nandnis an odd prime, thereby showing that Drisko’s method cannot be extended to encompass any of the three suggested cases. We also extend exact computation ton≤ 9, discuss asymptotics forLo/LE, and propose a generalization of the Alon-Tarsi conjecture.

A \emph{gerechte framework} is a partition of an $n \times n$ array into $n$ regions of $n$ cells each. A \emph{realization} of a gerechte framework is a latin square of order $n$ with the property that when its cells are partitioned by the framework, each region contains exactly one copy of each symbol. A \emph{gerechte design} is a gerechte framework together with a realization. We investigate gerechte frameworks where each region is a rectangle. It seems plausible that all such frameworks have realizations, and we present some progress towards answering this question. In particular, we show that for all positive integers $s$ and $t$, any gerechte framework where each region is either an $s \times t$ rectangle or a $t\times s$ rectangle is realizable., Comment: 14 pages, 12 figures

We show a one-to-one correspondence between arrangements of d lines in the projective plane, and lines in P^{d-2}. We apply this correspondence to classify (3,q)-nets over the complex numbers for all q, 19 pages, to appear in Advances in Geometry. Sections 5, 6 and 7 of old version are worked out in more detail at the beginning of "Arrangements of rational sections over curves and the varieties they define"

In this paper we study collections of mutually nearly orthogonal Latin squares ($\text{MNOLS}$), which come from a modification of the orthogonal condition for mutually orthogonal Latin squares. In particular, we find the maximum $\mu$ such that there exists a set of $\mu$ cyclic $\text{MNOLS}$ of order $n$ for $n \leq 18$, as well as providing a full enumeration of sets and lists of $\mu$ cyclic $\text{MNOLS}$ of order $n$ under a variety of equivalences with $n \leq 18$. This resolves in the negative a conjecture that proposed the maximum $\mu$ for which a set of $\mu$ cyclic $\text{MNOLS}$ of order $n$ exists is $\lceil n/4\rceil +1$., Comment: 18 pages

In this paper, constructions of multimagic squares are investigated. Diagonal Latin squares and Kronecker products are used to get some constructions of multimagic squares. Consequently, some new families of compound multimagic squares are obtained.

Orthogonal array based space-filling designs (Owen [Statist. Sinica 2 (1992a) 439-452]; Tang [J. Amer. Statist. Assoc. 88 (1993) 1392-1397]) have become popular in computer experiments, numerical integration, stochastic optimization and uncertainty quantification. As improvements of ordinary Latin hypercube designs, these designs achieve stratification in multi-dimensions. If the underlying orthogonal array has strength $t$, such designs achieve uniformity up to $t$ dimensions. Existing central limit theorems are limited to these designs with only two-dimensional stratification based on strength two orthogonal arrays. We develop a new central limit theorem for these designs that possess stratification in arbitrary multi-dimensions associated with orthogonal arrays of general strength. This result is useful for building confidence statements for such designs in various statistical applications., Comment: Published in at http://dx.doi.org/10.1214/14-AOS1231 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

A critical set in an n x n array is a set C of given entries, such that there exists a unique extension of C to an n x n Latin square and no proper subset of C has this property. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n), 10 pages, LaTeX

The generalized word length pattern of an orthogonal array allows a ranking of orthogonal arrays in terms of the generalized minimum aberration criterion (Xu and Wu [Ann. Statist. 29 (2001) 1066-1077]). We provide a statistical interpretation for the number of shortest words of an orthogonal array in terms of sums of $R^2$ values (based on orthogonal coding) or sums of squared canonical correlations (based on arbitrary coding). Directly related to these results, we derive two versions of generalized resolution for qualitative factors, both of which are generalizations of the generalized resolution by Deng and Tang [Statist. Sinica 9 (1999) 1071-1082] and Tang and Deng [Ann. Statist. 27 (1999) 1914-1926]. We provide a sufficient condition for one of these to attain its upper bound, and we provide explicit upper bounds for two classes of symmetric designs. Factor-wise generalized resolution values provide useful additional detail., Published in at http://dx.doi.org/10.1214/14-AOS1205 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

A paper by Cavenagh and Wanless diagnosed the possible intersection of any two transversals of the back circulant Latin square B_n, and used the result to completely determine the spectrum for 2-way k-homogeneous latin trades. We give a generalization of this problem for the intersection of \mu transversals of B_n and provide a construction for this problem, as well as providing base designs for the construction in the cases \mu= 3, 4 found by a computational search. This result is then applied to the problem of finding \mu-way k-homogeneous Latin trades. We generalize this problem to the intersection of \mu transversals of B_n such that the transversals intersect stably (that is, the intersection of any pair of transversals is independent of the choice of the pair) and show that these structures can be used to construct \mu-way k-homogeneous circulant latin trades of odd order. We provide a number of basic existence and non-existence results for \mu transversals of B_n that intersect stably, as well as the results of a computational search for small n. This is followed by the principal results of this paper; a construction that covers a large portion of the spectrum when n is sufficiently large, which requires certain base designs. These base designs are provided in the cases \mu= 3,4, which were found by a computational search. We use this result to find the existence of \mu-way k-homogeneous circulant latin trades of odd order, for \mu= 3, 4., Comment: 24 pages

A symmetry group for Sudoku is complete if its action partitions the set of Sudoku boards into all possible orbits, and minimal if no group of smaller size would do the same. Previously, for a 4 x 4 Sudoku variation known as Shidoku, the authors used an analogous symmetry group to partition the set of Shidoku boards into so-called "nests" and then use the interplay between the physical and relabeling symmetries to find certain subgroups that were both complete and minimal. In this paper these same techniques are applied to find a minimal complete symmetry group for the modular magic Sudoku variation, as well as for another Sudoku variation called semi-magic Sudoku. The paper concludes with a simple computation which leads to the non-obvious fact that the full Sudoku symmetry group is, in fact, already minimal and complete.

For prime powers q we use "strongly orthogonal" linear Sudoku solutions of order q^2 to construct ordered orthogonal arrays of type OOA (4,s,2,q), and for each q we present a range of values of s for which these constructions are valid., 18 pages

The aim of this note is to introduce a fast new general method for the construction of double and single even order magic squares. The method for double even order magic squares is fairly straight-forward but some adjustment is necessary for single even order magic squares., Comment: 9 pages; 10 figures

Mixed-level orthogonal arrays are basic structures in experimental design. We develop three algorithms that compute Rao- and Gilbert-Varshamov-type bounds for mixed-level orthogonal arrays. The computational complexity of the terms involved in the original combinatorial representations of these bounds can grow fast as the parameters of the arrays increase and this justifies the construction of these algorithms. The first is a recursive algorithm that computes the bounds exactly, the second is based on an asymptotic analysis, and the third is a simulation algorithm. They are all based on the representation of the combinatorial expressions that appear in the bounds as expectations involving a symmetric random walk. The Markov property of the underlying random walk gives the recursive formula to compute the expectations. A large deviation (LD) analysis of the expectations provides the asymptotic algorithm. The asymptotically optimal importance sampling (IS) of the same expectation provides the simulation algorithm. Both the LD analysis and the construction of the IS algorithm use a representation of these problems as a sequence of stochastic optimal control problems converging to a limit calculus of a variations problem. The construction of the IS algorithm uses a recently discovered method of using subsolutions to the Hamilton-Jacobi-Bellman equations associated with the limit problem.

Mixed level orthogonal arrays are basic structures in experimental design. We develop three algorithms that compute Rao and Gilbert-Varshamov type bounds for mixed level orthogonal arrays. The computational complexity of the terms involved in these bounds can grow fast as the parameters of the arrays increase and this justifies the construction of these algorithms. The first is a recursive algorithm that computes the bounds exactly, the second is based on an asymptotic analysis and the third is a simulation algorithm. They are all based on the representation of the combinatorial expressions that appear in the bounds as expectations involving a symmetric random walk. The Markov property of the underlying random walk gives the recursive formula to compute the expectations. A large deviation (LD) analysis of the expectations provide the asymptotic algorithm. The asymptotically optimal importance sampling (IS) of the same expectation provides the simulation algorithm. Both the LD analysis and the construction of the IS algorithm uses a representation of these problems as a sequence of stochastic optimal control problems converging to a limit calculus of variations problem. The construction of the IS algorithm uses a recently discovered method of using subsolutions to the Hamilton Jacobi Bellman equation associated with the limit problem., Comment: 28 pages, 2 figures

Let $P$ be a partial latin square of prime order $p>7$ consisting of three cyclically generated transversals. Specifically, let $P$ be a partial latin square of the form: \[ P=\{(i,c+i,s+i),(i,c'+i,s'+i),(i,c''+i,s''+i)\mid 0 \leq i< p\} \] for some distinct $c,c',c''$ and some distinct $s,s',s''$. In this paper we show that any such $P$ completes to a latin square which is diagonally cyclic., 13 pages, SAGE source code

A (partial) Latin square is a table of multiplication of a (partial) quasigroup. Multiplication of a (partial) quasigroup may be considered as a set of triples. We give a necessary and sufficient condition for a set of triples to be a quotient of a (partial) latin square.

In this paper we determine a class of critical sets in the abelian {2--group} that may be obtained from a greedy algorithm. These new critical sets are all 2--critical (each entry intersects an intercalate, a trade of size 4) and completes in a top down manner., Comment: 25 pages

The asymptotic form of the number of n-quasigroups of order 4 is $3^{n+1} 2^{2^n +1} (1+o(1))$. Keywords: n-quasigroups, MDS codes, decomposability, reducibility., Comment: 15 p., 3 fig

A Latin square $L(n,k)$ is a square of order $n$ with its entries colored with $k$ colors so that all the entries in a row or column have different colors. Let $d(L(n,k))$ be the minimal number of colored entries of an $n \times n$ square such that there is a unique way of coloring of the yet uncolored entries in order to obtain a Latin square $L(n, k)$. In this paper we discuss the properties of $d(L(n,k))$ for $k=2n-1$ and $k=2n-2$. We give an alternate proof of the identity $d(L(n, 2n-1))=n^2-n$, which holds for even $n$, and we establish the new result $d(L(n, 2n-2)) \geq n^2-\lfloor\frac{8n}{5}\rfloor$ and show that this bound is tight for $n$ divisible by 10., Comment: 16 pages, 24 figures

In 1990, Kolesova, Lam and Thiel determined the 283,657 main classes of Latin squares of order 8. Using techniques to determine relevant Latin trades and integer programming, we examine representatives of each of these main classes and determine that none can contain a uniquely completable set of size less than 16. In three of these main classes, the use of trades which contain less than or equal to three rows, columns, or elements does not suffice to determine this fact. We closely examine properties of representatives of these three main classes. Writing the main result in Nelder's notation for critical sets, we prove that scs(8)=16., Comment: 10 pages

This is a translation of Leonhard Euler's ``De quadratis magicis'' . It is E795 in the Enestrom index. This paper studies how to construct magic squares with certain numbers of cells, in particular 9, 16, 25 and 36. It considers some general rules for making squares of even and odd orders. Euler uses Graeco-Latin squares and constrains the values that the variables can take to make magic squares. I think this is where the terms ``Latin'' and ``Graeco-Latin'' square comes from, since he uses Latin letters in one square and Greek (i.e. ``Graeco'') letters in another for each construction. (This paper was published before Euler's only other paper ``Recherches sur une nouvelle espece de quarres magiques'' E530 about Latin squares was, in 1782.), Comment: 15 pages, translation of the original Latin ``De quadratis magicis'', Commentationes arithmeticae 2 (1849), 593-602

We use a greedy probabilistic method to prove that for every $\epsilon > 0$, every $m\times n$ Latin rectangle on $n$ symbols has an orthogonal mate, where $m=(1-\epsilon)n$. That is, we show the existence of a second Latin rectangle such that no pair of the $mn$ cells receives the same pair of symbols in the two rectangles., Comment: Accepted for publication in CPC

A Poisson-Voronoi tessellation (PVT) is a tiling of the Euclidean plane in which centers of individual tiles constitute a Poisson field and each tile comprises the locations that are closest to a given center with respect to a prescribed norm. Many spatial systems in which rare, randomly distributed centers compete for space should be well approximated by a PVT. Examples that we can handle rigorously include multitype threshold vote automata, in which $\kappa$ different camps compete for voters stationed on the two-dimensional lattice. According to the deterministic, discrete-time update rule, a voter changes affiliation only to that of a unique opposing camp having more than $\theta$ representatives in the voter's neighborhood. We establish a PVT limit for such dynamics started from completely random configurations, as the number of camps becomes large, so that the density of initial "pockets of consensus" tends to 0. Our methods combine nucleation analysis, Poisson approximation, and shape theory.

We develop a combinatorial condition necessary for the existence of a saturated asymmetrical orthogonal array of strength 2. This condition limits the choice of integral solutions to the system of equations in the Bose-Bush approach and can thus strengthen considerably the Bose-Bush approach as applied to a symmetrical part of such an array. As a consequence, several nonexistence results follow for saturated and nearly saturated orthogonal arrays of strength 2. One of these leads to a partial settlement of an issue left open in a paper by Wu, Zhang and Wang. Nonexistence of a class of saturated asymmetrical orthogonal arrays of strength 4 is briefly discussed.

Randomized orthogonal arrays provide good sets of input points for exploration of computer programs and for Monte Carlo integration. In 1954, Patterson gave a formula for the randomization variance of the sample mean of a function evaluated at the points of an orthogonal array. That formula is incorrect for most of the arrays that are practical for computer experiments. In this paper we correct Patterson's formula. We also remark on a defect, related to coincidences, in some orthogonal arrays. These are arrays of the form $OA(2q^2, 2q + 1, q, 2)$, where $q$ is a prime power, obtained by constructions due to Bose and Bush and to Addelman and Kempthorne. We conjecture that subarrays of the form $OA(2q^2, 2q, q, 2)$ may be constructed to avoid this defect.

Constructive and nonconstructive techniques are employed to enumerate Latin squares and related objects. It is established that there are (i) 2036029552582883134196099 main classes of Latin squares of order 11; (ii) 6108088657705958932053657 isomorphism classes of one-factorizations of $K_{11,11}$; (iii) 12216177315369229261482540 isotopy classes of Latin squares of order 11; (iv) 1478157455158044452849321016 isomorphism classes of loops of order 11; and (v) 19464657391668924966791023043937578299025 isomorphism classes of quasigroups of order 11. The enumeration is constructive for the 1151666641 main classes with an autoparatopy group of order at least 3., Comment: Minor revision; to appear in Mathematics of Computation