Search

A Latin square of order $n$ is an $n\times n$ matrix in which each row and column contains each of $n$ symbols exactly once. For $\epsilon>0$, we show that with high probability a uniformly random Latin square of order $n$ has no proper subsquare of order larger than $n^{1/2}\log^{1/2+\epsilon}n$. Using this fact we present a canonical labelling algorithm for Latin squares of order $n$ that runs in average time bounded by a polynomial in $n$. The algorithm can be used to solve isomorphism problems for many combinatorial objects that can be encoded using Latin squares, including quasigroups, Steiner triple systems, Mendelsohn triple systems, $1$-factorisations, nets, affine planes and projective planes., Comment: New reference added, minor typos fixed

Orthogonal array and a large set of orthogonal arrays are important research objects in combinatorial design theory, and they are widely applied to statistics, computer science, coding theory and cryptography. In this paper, some new series of large sets of orthogonal arrays are given by direct construction, juxtaposition construction, Hadamard construction, finite field construction and difference matrix construction. Subsequently, many new infinite classes of orthogonal arrays are obtained by using these large sets of orthogonal arrays and Kronecker product., Comment: 38 pages, 6 Tables

A $d$-dimensional Latin hypercube of order $n$ is a $d$-dimensional array containing symbols from a set of cardinality $n$ with the property that every axis-parallel line contains all $n$ symbols exactly once. We show that for $(n, d) \notin \{(4,2), (6,2)\}$ with $d \geq 2$ there exists a $d$-dimensional Latin hypercube of order $n$ that contains no $d$-dimensional Latin subhypercube of any order in $\{2,\dots,n-1\}$. The $d=2$ case settles a 50 year old conjecture by Hilton on the existence of Latin squares without proper subsquares.

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

A \emph{frequency square} is a matrix in which each row and column is a permutation of the same multiset of symbols. Two frequency squares $F_1$ and $F_2$ with symbol multisets $M_1$ and $M_2$ are \emph{orthogonal} if the multiset of pairs obtained by superimposing $F_1$ and $F_2$ is $M_1\times M_2$. A set of MOFS is a set of frequency squares in which each pair is orthogonal. We first generalise the classical bound on the cardinality of a set of MOFS to cover the case of \emph{mixed type}, meaning that the symbol multisets are allowed to vary between the squares in the set. A frequency square is \emph{binary} if it only uses the symbols 0 and 1. We say that a set $\mathcal{F}$ of MOFS is \emph{type-maximal} if it cannot be extended to a larger set of MOFS by adding a square whose symbol multiset matches that of at least one square already in $\mathcal{F}$. Building on pioneering work by Stinson, several recent papers have found conditions that are sufficient to show that a set of binary MOFS is type-maximal. We generalise these papers in several directions, finding new conditions that imply type-maximality. Our results cover sets of binary frequency squares of mixed type. Also, where previous papers used parity arguments, we show the merit of arguments that use moduli greater than 2.

In this paper, we study skew frame starters, which are strong frame starters that satisfy an additional "skew" property. We prove three new non-existence results for cyclic skew frame starters of certain types. We also construct several small examples of previously unknown cyclic skew frame starters by computer.

A transversal in an $n \times n$ latin square is a collection of $n$ entries not repeating any row, column, or symbol. Kwan showed that almost every $n \times n$ latin square has $\bigl((1 + o(1)) n / e^2\bigr)^n$ transversals as $n \to \infty$. Using a loose variant of the circle method we sharpen this to $(e^{-1/2} + o(1)) n!^2 / n^n$. Our method works for all latin squares satisfying a certain quasirandomness condition, which includes both random latin squares with high probability as well as multiplication tables of quasirandom groups., Comment: 26 pages, 3 figures. Final version incorporating referee's comments. To appear in Proceedings of the London Mathematical Society

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 partial Latin square of order $n$ can be represented by a $3$-dimensional chess-board of size $n\times n\times n$ with at most $n^2$ non-attacking rooks. Based on this representation, we apply a uniform method to prove the M. Hall's, Ryser's and Cruse's theorems for completion of partial Latin squares. With the help of this proof, we extend the scope of Cruse's theorem to compact bricks, which appear to be independent of their environment. Without losing any completion you can replace a dot by a rook if the dot must become rook, or you can eliminate the dots that are known not to become rooks. Therefore, we introduce primary and secondary extension procedures that are repeated as many times as possible. If the procedures do not decide whether a PLSC can be completed or not, a new necessary condition for completion can be formulated for the dot structure of the resulting PLSC, the BUG condition.

A partial Latin square of order $n$ can be represented by a $3$-dimensional chess-board of size $n\times n\times n$ with at most $n^2$ non-attacking rooks. In Latin squares, a subsystem and its most distant mate together have as many rooks as their capacity. That implies a simple capacity condition for the completion of partial Latin squares which is in fact the Cruse's necessary condition for characteristic matrices. Andersen-Hilton proved that, except for certain listed cases, a PLS of order $n$ can be completed if it contains only $n$ symbols. Andersen proved it for $n+1$ symbols, listing the cases to be excluded. Identifying the structures of the chess-board that can be overloaded with $n$ or $n+1$ rooks, it follows that a PLS derived from a chess-board with at most $n+1$ non-attacking rooks can be completed exactly if it satisfies the capacity condition. In a layer of a Latin square, two subsystems of a remote couple are in balance. Thus, a necessary condition for completion of a layer can be formulated, the balance condition. For an LSC, each 1-dimensional subspace of the chess-board contains exactly one rook. Consequently, for the PLSCs derived from partial Latin squares, we examine certain sets of 1-dimensional subspaces because they indicate the number of missing rooks.

A $d$-dimensional generalization of a Latin square of order $n$ can be considered as a chess-board of size $n\times n\times \ldots\times n$ ($d$ times), containing $n^d$ cells with $n^{d-1}$ non-attacking rooks. Each cell is identified by a $d$-tuple $(e_1,e_2,\ldots ,e_d)$ where $e_i \in \{1,2,\ldots ,n\}$. For $d = 3$ we prove that such a chess-board represents precisely one main class. A subsystem $T$ induced by a family of sets $$ over $\{1,2,\ldots ,n\}$ is real if $E_i \subset \{1,2,\ldots ,n\}$ for each $i \in \{1,2,\ldots ,d\}$. The density of $T$ is the ratio of contained rooks to the number of cells in $T$. The distance between two subsystems is the minimum Hamming distance between cell pairs. Replacing $k$ sets of $$ by their complements, a subsystem $U$ is obtained with distance $k$ between $T$ and $U$. All these subsystems, including $T$, form a partition of the chess-board. We prove that in such a partition, the number of rooks in a $U$ and the density of $U$ can be determined from the number of rooks in $T$ and the number of cells in $T$ and $U$ and the value of $(-1)^k$. We examine the subsystem couple $(T,U)$ in the $2$- and $3$-dimensional cases, where $U$ is the most distant unique subsystem from a real $T$. On the fly, a new identity of binomial coefficients is proved.

A relation on a $k$-net$(n)$ (or, equivalently, a set of $k-2$ mutually orthogonal Latin squares of order $n$) is an $\mathbb{F}_{2}$ linear dependence within the incidence matrix of the net. Dukes and Howard (2014) showed that any 6-net(10) satisfies at least two non-trivial relations, and classified the relations that could appear in such a net. We find that, up to equivalence, there are $18\,526\,320$ pairs of MOLS satisfying at least one non-trivial relation. None of these pairs extend to a triple. We also rule out one other relation on a set of $3$-MOLS from Dukes and Howard's classification.

E. R. Lamken prove in [5] that there exists a partitioned balanced tournament design of side $n$, PBTD($n$), for $n$ a positive integer, $n \ge 5$, except possibly for $n \in \{9,11,15\}$. In this article, we show the existence of PBTD($n$) for $n \in \{9,11,15\}$. As a consequence, the existence of PBTD($n$) has been completely determined.

A $(v, k, \lambda)$ symmetric design is said to have the symmetric difference property (SDP) if the symmetric difference of any three blocks is either a block or the complement of a block. Symmetric designs fulfilling this property have the nice property of having minimal rank, which makes them interesting to study. Thus, SDP designs become useful in coding theory applications. We show in this paper that difference sets formed by direct product construction of difference sets whose developments have the SDP also have the SDP. We also establish a few results regarding isomorphisms in product constructed SDP designs., Comment: 9 pages

An embedding of a code is a mapping that preserves distances between codewords. We prove that any code with code distance $\rho$ and length $d$ can be embedded into an MDS code with the same code distance and length but under a larger alphabet. As a corollary we obtain embeddings of systems of partial mutually orthogonal Latin cubes and $n$-ary quasigroups., Comment: 7 pages

A Latin square of order $n$ is an $n\times n$ array which contains $n$ distinct symbols exactly once in each row and column. We define the adjacent distance between two adjacent cells (containing integers) to be their difference modulo $n$, and inner distance of a Latin square to be the minimum of adjacent distances in the Latin square. By first establishing upper bounds and then constructing squares with said inner distance, we found the maximum inner distance of an $n \times n$ Latin square to be $\left\lfloor\frac{n-1}{2}\right\rfloor$. We then studied special kinds of Latin squares such as pandiagonals (also known as Knut-Vik designs), as well as Sudoku Latin squares. This research was conducted at the REU at Moravian College on Research Challenges of Computational and Experimental Mathematics, with support from the National Science Foundation., Comment: This research was done as part of an REU at Moravian College. This was supported by the NSF Grant Number DMS-1852378

We settle the existence of certain "anti-magic" cubes using combinatorial block designs and graph decompositions to align a handful of small examples.

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

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

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

We show that no orthogonal arrays $OA(16 \lambda, 11, 2,4)$ exist with $\lambda=6$ and $\lambda=7$. This solves an open problem of the NSUCRYPTO Olympiad 2018. Our result allows us to determine the minimum weights of certain higher-order correlation-immune Boolean functions.

In an earlier paper by three of the present authors and Csaba Schneider, it was shown that, for $m\ge2$, a set of $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$), 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$ partitions with $r\geq 2$, any $m$ of which are minimal elements of a Cartesian lattice. If $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$, things are more restricted. Any $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. Under this hypothesis, such a 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$ in the $(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.

We develop a limit theory of Latin squares, paralleling the recent limit theories of dense graphs and permutations. We introduce a notion of density, an appropriate version of the cut distance, and a space of limit objects - so-called Latinons. Key results of our theory are the compactness of the limit space and the equivalence of the topologies induced by the cut distance and the left-convergence. Last, using Keevash's recent results on combinatorial designs, we prove that each Latinon can be approximated by a finite Latin square., Comment: 66 pages, 1 figure, final version published in Discrete Analysis

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 [Electron. J. Combin. 27(3) (2020), P3.7] 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'\le 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\le v-uh