Balanced equi-\(n\)-squares (Q2205119)

Summary: We define a \(d\)-balanced equi-\(n\)-square \(L=(l_{ij})\), for some divisor \(d\) of \(n\), as an \(n \times n\) matrix containing symbols from \(\mathbb{Z}_n\) in which any symbol that occurs in a row or column, occurs exactly \(d\) times in that row or column. We show how to construct a \(d\)-balanced equi-\(n\)-square from a partition of a Latin square of order \(n\) into \(d \times (n/d)\) subrectangles. In graph theory, \(L\) is equivalent to a decomposition of \(K_{n,n}\) into \(d\)-regular spanning subgraphs of \(K_{n/d,n/d}\). We also study when \(L\) is diagonally cyclic, defined as when \(l_{(i+1)(j+1)}=l_{ij}+1\) for all \(i,j \in \mathbb{Z}_n\), which correspond to cyclic such decompositions of \(K_{n,n}\) (and thus \(\alpha\)-labellings). We identify necessary conditions for the existence of (a) \(d\)-balanced equi-\(n\)-squares, (b) diagonally cyclic \(d\)-balanced equi-\(n\)-squares, and (c) Latin squares of order \(n\) which partition into \(d \times (n/d)\) subrectangles. We prove the necessary conditions are sufficient for arbitrary fixed \(d \geqslant 1\) when \(n\) is sufficiently large, and we resolve the existence problem completely when \(d \in \{1,2,3\}\). Along the way, we identify a bijection between \(\alpha\)-labellings of \(d\)-regular bipartite graphs and what we call \(d\)-starters: matrices with exactly one filled cell in each top-left-to-bottom-right unbroken diagonal, and either \(d\) or \(0\) filled cells in each row and column. We use \(d\)-starters to construct diagonally cyclic \(d\)-balanced equi-\(n\)-squares, but this also gives new constructions of \(\alpha\)-labellings.