Latin cubes with disjoint subcubes of two orders

Tara Kemp, James Lefevre · 2025

Read Latin cubes with disjoint subcubes of two orders by Tara Kemp, James Lefevre (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-06768.txt.

Introduction

Tara Kemp and James G Lefevre work on Latin cubes, the three-dimensional cousins of Latin squares and Sudoku-like arrays. A Latin cube can contain smaller disjoint subcubes, and given a list of subcube sizes that add up to the whole order, the question is whether such a cube exists. For Latin squares with subsquares of at most two sizes, existence is fully settled, but the cube version was only partially solved.

Restricting to subcubes of two orders, the authors determine existence in almost all cases. Their constructions and impossibility arguments close nearly the whole problem, leaving only a small residue of undecided parameter combinations. The result extends a classic line of combinatorial design theory from two dimensions to three, where the extra dimension changes which size combinations can be realized.

Catalog record

CREATORTara Kemp, James Lefevre
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE172 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-06768

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Latin cubes with disjoint subcubes of two orders Tara Kemp, James Lefevre Abstract Given a partition h 1 + h 2 + ⋯ + h k = n h_{1}+h_{2}+\dots+h_{k}=n , a latin square of order n n with pairwise disjoint subsquares of orders h 1 ​ … ​ h k h_{1}\dots h_{k} is called a realization. When the values h i h_{i} are of at most two sizes, the existence of a realization has been completely determined. However, the existence of a latin cube with pairwise disjoint subcubes of two orders is only partially solved. In this paper, we determine existence for such latin cubes in almost all cases. 1 Preliminaries The study of latin squares with sets of pairwise disjoint subsquares was originally motivated by a question posed by L. Fuchs [ 8 ] about quasigroups with disjoint subquasigroups. Although much work has been done, the problem of existence of such latin squares remains unsolved. The original problem requires that the orders of the subsquares partition the order of the latin square, and in that case existence has been completely determined when the subsquares are of at most two different orders or there are at most five subsquares. An analogous problem has been defined for latin cubes and latin hypercubes in [ 3 ] , and the same first case, where the subcubes are of at most two orders, is only partially solved. A latin square of order n is an n\times n array, L , with symbols from [n]=\{1,2,\dots,n\} such that each symbol occurs exactly once in each row and column. The notation a+[n] represents the set \{a+i\mid i\in[n]\} . A subsquare of order m is an m\times m subarray of L that is itself a latin square of order m . It is well-known that for any subsquare, if m\neq n then m\leq\frac{n}{2} [ 4 ] . An orthogonal array with strength t , k constraints, n levels and index \lambda , denoted \OA_{\lambda}(t,k,n) , is a k\times(\lambda n^{t}) array A with n symbols such that each possible t -tuple of symbols occurs exactly \lambda times as a column in any t -rowed subarray of A . If \lambda=1 , then it is often omitted. A latin square of order n is equivalent to an \OA(2,3,n) , and so orthogonal arrays can be used to generalise latin squares into higher dimensions. There are competing definitions for latin cubes, equivalent to either an \OA_{n}(2,4,n) or \OA(3,4,n) . The latter are sometimes called permutation cubes and that is the type we consider here. Thus, a latin cube of order n is an n\times n\times n array C with n symbols such that each symbol occurs exactly once in each line of C , where a line is a set of n cells found by fixing two of the three coordinates. Lines are denoted by (i,j,[n]) , (i,[n],j) or ([n],i,j) and referred to respectively as files, rows and columns. A layer is a set of cells with one fixed coordinate and represented by (i,[n],[n]) , ([n],i,[n]) or ([n],[n],i) . The notation (A,B,C) represents the set of cells \{(i,j,k)\mid i\in A,j\in B,k\in C\} , and a \cdot in place of any of the sets represents [n] . A subcube of order m is defined similarly to a subsquare; an m\times m\times m subarray of C that is itself a latin cube of order m . Two subcubes are disjoint if they share no layer or symbol. Example 1.1 . The arrays in Figure 1 are the layers of an order 5 latin cube with three pairwise disjoint subcubes. The subcubes are highlighted. \begin{array}[]{|ccccc|}\hline\cr\pagecolor{lightgray}1&\pagecolor{lightgray}2&3&5&4\\ \pagecolor{lightgray}2&\pagecolor{lightgray}1&5&4&3\\ 3&5&4&2&1\\ 4&3&2&1&5\\ 5&4&1&3&2\\ \hline\cr\end{array} \begin{array}[]{|ccccc|}\hline\cr\pagecolor{lightgray}2&\pagecolor{lightgray}1&5&4&3\\ \pagecolor{lightgray}1&\pagecolor{lightgray}2&4&3&5\\ 4&3&1&5&2\\ 5&4&3&2&1\\ 3&5&2&1&4\\ \hline\cr\end{array} \begin{array}[]{|ccccc|}\hline\cr 5&3&4&1&2\\ 3&4&2&5&1\\ 1&2&\pagecolor{lightgray}3&4&\pagecolor{lightgray}5\\ 2&5&1&3&4\\ 4&1&\pagecolor{lightgray}5&2&\pagecolor{lightgray}3\\ \hline\cr\end{array} \begin{array}[]{|ccccc|}\hline\cr 4&5&2&3&1\\ 5&3&1&2&4\\ 2&4&\pagecolor{lightgray}5&1&\pagecolor{lightgray}3\\ 3&1&4&5&2\\ 1&2&\pagecolor{lightgray}3&4&\pagecolor{lightgray}5\\ \hline\cr\end{array} \begin{array}[]{|ccccc|}\hline\cr 3&4&1&2&5\\ 4&5&3&1&2\\ 5&1&2&3&4\\ 1&2&5&\pagecolor{lightgray}4&3\\ 2&3&4&5&1\\ \hline\cr\end{array} Figure 1 : An order 5 latin cube with disjoint subcubes. We define partial latin squares and cubes here, as they are needed in later sections. A partial latin square of order n is an n\times n array in which each cell contains at most one symbol from [n] and each symbol occurs at most once in each row and column. An r\times s array with symbols from [n] , where n\geq r,s , is a latin rectangle if each symbol occurs at most once in each row and column. There are analogous definitions for latin cubes. A partial latin cube is an n\times n\times n array such that each cell contains at most one symbol from [n] and each symbol occurs at most once in each line. A latin box is an r\times s\times t array with n\geq r,s,t symbols such that each symbol occurs at most once in each line. Similarly, a partial \OA_{\lambda}(t,k,n) is a k\times m array A , for some m\leq\lambda n^{t} , with n symbols such that each possible t -tuple of symbols occurs at most \lambda times as a column in any t -rowed subarray of A . If the empty cells of a partial latin square (or cube) L can be filled with symbols from [n] to form a latin square (cube) L^{\prime} , then we say that L can be completed and L^{\prime} is a completion of L . Throughout, we use P=(h_{1}\dots h_{k}) or (h_{1}^{\alpha_{1}}h_{2}^{\alpha_{2}}\dots h_{m}^{\alpha_{m}}) to represent a partition of n with \sum_{i=1}^{k}h_{i}=n or \sum_{i=1}^{m}\alpha_{i}h_{i}=n . Returning to latin squares and the problem introduced by L. Fuchs, a realization of a partition P=(h_{1}\dots h_{k}) of n , denoted \LS(h_{1}\dots h_{k}) or just \text{RP}(h_{1}\dots h_{k}) , is a latin square of order n with pairwise disjoint subsquares of orders h_{1},h_{2},\dots,h_{k} . The subsquares must be row, column and symbol disjoint. Relevant to this work are the results of Dénes and Pásztor [ 2 ] , Heinrich [ 6 , 5 ] and Kuhl and Schroeder [ 9 ] . Theorem 1.2 ( [ 2 ] ) . For k\geq 1 and a\geq 1 , a \LS(a^{k}) exists if and only if k\neq 2 . Theorem 1.3 ( [ 6 ] , [ 5 ] , Theorem 5.1 of [ 9 ] ) . For a>b>0 and k\geq 4 , a \LS(a^{u}b^{k-u}) exists if and only if u\geq 3 , or u\in[2] and a\leq(k-2)b except when k=4 and u=2 . Given a partition P of n , a 3-realization of P , denoted \LC(h_{1}\dots h_{k}) , is a latin cube of order n with pairwise disjoint subcubes of orders h_{1},\dots,h_{k} . Unless otherwise stated, we assume that h_{1}\geq h_{2}\geq\dots\geq h_{k}>0 . The latin cube in Example 1.1 is a \LC(2^{2}1^{1}) . A 3-realization is in normal form if for each m\in[k] and i,j,\ell\in H_{m} , the cell (i,j,\ell) contains a symbol from H_{m} , where H_{m}=\sum_{i=1}^{m-1}h_{i}+[h_{m}] . A 3-realization in normal form has the subcubes along the main diagonal, with the orders of the subcubes in decreasing order and the symbols used in each subcube in increasing order (note that this is a stronger condition than the one given in [ 3 ] ). Any 3-realization can be put into normal form via an appropriate permutation of layers and symbols. The results in [ 3 ] focus on partitions with at most two distinct integers and correspond

Read the complete text