Mutually orthogonal anti-Latin squares
Abstract
Anti-Latin squares were introduced in connection with non-linear secure network coding, and the extremal problem for large mutually orthogonal families is motivated by that setting. We study the maximum size NA(d) of a family of mutually orthogonal anti-Latin squares of order d. We prove that NL(d)+1≤ NA(d)≤ NL(d)+2 for every d≥ 3, where NL(d) denotes the classical maximum size of a family of mutually orthogonal Latin squares of order d, and we show that in fact NA(3)=NL(3)+1 whereas NA(d)=NL(d)+2 for every d≥ 4. The upper bound is obtained by passing through balanced matrices, while the lower bound is given by a deterministic permutation argument. For all d≥ 8, and also for the exceptional order d=6, the upper bound is shown to be attainable by a general probabilistic construction. On the structural side, we show that a saturated family of size d+1 induces an affine plane of order d, and that the saturated case is characterized by the existence of an anti-coordinate grid decomposition; after transporting this condition to the fixed cell set [d]2, it becomes a direction-completeness condition on the corresponding row-blocks and column-blocks. The remaining small orders are treated separately: d=3 is handled by direct analysis and classification of orthogonal triples, d=4 by an explicit saturated construction and an analysis of its finite-geometric structure, and d=5 and d=7 by explicit saturated examples arising from the random-grid framework. Thus NA(d) is determined in terms of NL(d) for every d≥3, and its numerical value is obtained explicitly for every 3≤ d≤9.
Related
- Orthogonal Quantum Latin Squares with Maximal Cardinality from Full-Rank Factorizations
- Symmetric Quantum Latin Squares with Maximal Cardinality
- Resolvable quantum Latin squares with maximal cardinality
- Latin Squares with Few Transversals
- Counting Near-Spanning Matchings in Latin Squares and Steiner Triple Systems
BibTeX
@misc{aoyama2026mutually,
title = {{Mutually orthogonal anti-Latin squares}},
author = {Eishiro Aoyama and So Hasegawa and Masahito Hayashi and Tomoki Sagara},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.30082},
eprint = {2608.30082},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.30082},
}
RIS
TY - UNPB
TI - Mutually orthogonal anti-Latin squares
AU - Eishiro Aoyama
AU - So Hasegawa
AU - Masahito Hayashi
AU - Tomoki Sagara
PY - 2026
DA - 2026/08/30
PB - arXiv
DO - 10.48550/arxiv.2608.30082
UR - https://arxiv.org/abs/2608.30082
AB - Anti-Latin squares were introduced in connection with non-linear secure network coding, and the extremal problem for large mutually orthogonal families is motivated by that setting. We study the maximum size N_A(d) of a family of mutually orthogonal anti-Latin squares of order d. We prove that N_L(d)+1≤ N_A(d)≤ N_L(d)+2 for every d≥ 3, where N_L(d) denotes the classical maximum size of a family of mutually orthogonal Latin squares of order d, and we show that in fact N_A(3)=N_L(3)+1 whereas N_A(d)=N_L(d)+2 for every d≥ 4. The upper bound is obtained by passing through balanced matrices, while the lower bound is given by a deterministic permutation argument. For all d≥ 8, and also for the exceptional order d=6, the upper bound is shown to be attainable by a general probabilistic construction. On the structural side, we show that a saturated family of size d+1 induces an affine plane of order d, and that the saturated case is characterized by the existence of an anti-coordinate grid decomposition; after transporting this condition to the fixed cell set [d]^2, it becomes a direction-completeness condition on the corresponding row-blocks and column-blocks. The remaining small orders are treated separately: d=3 is handled by direct analysis and classification of orthogonal triples, d=4 by an explicit saturated construction and an analysis of its finite-geometric structure, and d=5 and d=7 by explicit saturated examples arising from the random-grid framework. Thus N_A(d) is determined in terms of N_L(d) for every d≥3, and its numerical value is obtained explicitly for every 3≤ d≤9.
ER -