The maximum number of transversals in $d$-dimensional Latin hypercubes at every order (Glebov–Luria conjecture)

The 2016 paper 'On the maximum number of Latin transversals' by Glebov and Luria determined the asymptotic maximum number of transversals in an order-$n$ Latin square, $T(n)=((1+o(1))n/e^2)^n$, and posed several follow-up enumeration questions. Of these, the typical-distribution question is now settled affirmatively (Kwan 2020, sharpened by Eberhard–Manners–Mrazović 2023), Vardi's 1991 conjecture on the cyclic Latin square is settled with optimal constants (Eberhard–Manners–Mrazović 2018), and Glebov–Luria's Question 4.2 on the minimum count $t(n)$ for odd $n$ is refuted (Dai–Divoux–Kelly 2025). The remaining open question is the higher-dimensional conjecture: for every fixed dimension $d≥3$, does the maximum number $T(d,N)$ of transversals in an order-$N$ $d$-dimensional Latin hypercube satisfy $T(d,N)≥((1-o(1))N^{d-1}/e^d)^N$ at every order $N$, extending Glebov–Luria's Theorem 4.1 beyond the infinitely many orders $N=kn^d$ reached by their construction? Together with Taranenko's general upper bound, this asks whether $T(d,N)=((1+o(1))N^{d-1}/e^d)^N$ for every fixed $d≥3$ and all $N→∞$.

Background

An order-$n$ Latin square is an $n×n$ array filled with $n$ symbols so that each symbol appears exactly once in every row and every column. A transversal of such a square is a selection of $n$ cells, no two of which share a row, a column, or a symbol. Writing $T(L)$ for the number of transversals of a square $L$, and $T(n)$ and $t(n)$ for the maximum and minimum of $T(L)$ over all order-$n$ Latin squares, counting transversals is a classical enumeration problem. McKay, McLeod and Wanless (2006) proved $b^n ≤ T(n) ≤ c^n n^{1/2} n!$ for constants $b≈1.719$ and $c≈0.614$. Taranenko (2015), developing the theory of permanents of multidimensional matrices, improved the upper bound to $T(n) ≤ ((1+o(1))n/e^2)^n$, and more generally proved that for every fixed $d≥2$ the maximum number of transversals in an order-$n$ $d$-dimensional Latin hypercube satisfies $T(d,n) ≤ ((1+o(1))n^{d-1}/e^d)^n$; here $o(1)$ denotes a quantity tending to $0$ as $n→∞$ with $d$ fixed. Glebov and Luria (2016) proved the matching lower bound $T(n) ≥ ((1-o(1))n/e^2)^n$ for every order $n$ — before their work not even a superexponential lower bound for $T(n)$ was known — so $T(n)=((1+o(1))n/e^2)^n$.

A $d$-dimensional Latin hypercube of order $n$ is an $[n]^d$ array over $n$ symbols in which every symbol appears exactly once in every line, a line being the set of entries obtained by fixing all coordinates but one; for $d=2$ this is exactly a Latin square. Equivalently, such a hypercube is a $(d+1)$-dimensional $0$-$1$ array with exactly one $1$ in every line, and a transversal is a set of $n$ chosen $1$-entries meeting every hyperplane (each value of each coordinate, and each symbol) exactly once. The number of transversals equals the multidimensional permanent of the representing array — the number of its diagonals, i.e. sets of $n$ entries no two of which lie in a common hyperplane — so $T(d,n)$ is the maximum permanent of an order-$n$ multidimensional permutation array. Glebov and Luria's probabilistic construction produces hypercubes achieving $T(d,N) ≥ ((1-o(1))N^{d-1}/e^d)^N$, but only at orders of the special form $N=kn^d$ dictated by the block structure of the construction (their Theorem 4.1).

The open question is the extension to every order. For squares ($d=2$) Glebov and Luria reach every order by a padding argument: from a transversal-rich order-$N$ square they build, for every $N'$ in a long window above $N$, an order-$N'$ square whose transversals include those of the original block, and the windows overlap so as to cover all large orders. No analogue of this completion step is known for hypercubes, and Glebov and Luria state only that they 'strongly believe' the bound holds for every value of $N$. The question sits in an active landscape on the existence side as well: hypercube analogues of group addition tables can fail to have transversals at all (the $d$-dimensional iterated addition table $H(x_1,…,x_d)=x_1+\cdots+x_d$ of a group without a complete mapping — a permutation $π$ of the group such that $x↦π(x)-x$ is also a permutation — has no transversal when $d$ is even, while for odd $d$ it has one), and Child and Wanless constructed, for every even dimension $d$ and every even order $n ≥ 10$, Latin hypercubes that have transversals but all of whose transversals are forced to meet a single fixed $(d-2)$-plane (the subarray obtained by fixing two coordinates), with some entries lying in no transversal at all. These obstructions concern particular hypercubes, however, whereas $T(d,N)$ maximizes over all hypercubes of a given order, so no order is excluded from the conjecture a priori.

Problem Statement

For every fixed integer $d ≥ 3$, is it true that the maximum number $T(d,N)$ of transversals in an order-$N$ $d$-dimensional Latin hypercube satisfies $T(d,N) ≥ \left((1-o(1))\frac{N^{d-1}}{e^d}\right)^{N}$ for every order $N$, where $o(1) → 0$ as $N → ∞$ with $d$ fixed? Glebov and Luria proved this for infinitely many orders $N$ (those of the form $N=kn^d$ produced by their probabilistic construction) and stated their strong belief that it holds for every value of $N$. Since Taranenko's complementary upper bound $T(d,N) ≤ ((1+o(1))N^{d-1}/e^d)^N$ holds for every $d ≥ 2$ and all $N → ∞$, an affirmative answer is equivalent to the asymptotic $T(d,N)=((1+o(1))N^{d-1}/e^d)^N$ holding at every order for each fixed $d ≥ 3$, exactly as it does for Latin squares ($d=2$). A complete resolution is either a proof covering all $d ≥ 3$ and all sufficiently large $N$, or a disproof: some fixed $d ≥ 3$, some $δ>0$, and infinitely many orders $N → ∞$ with $T(d,N) ≤ ((1-δ)N^{d-1}/e^d)^N$.

References

1. R. Glebov and Z. Luria. On the maximum number of Latin transversals. Journal of Combinatorial Theory, Series A 141 (2016) 136–146. doi:10.1016/j.jcta.2016.02.007, arXiv:1506.00983, https://arxiv.org/abs/1506.00983
2. A. A. Taranenko. Multidimensional permanents and an upper bound on the number of transversals in Latin squares. Journal of Combinatorial Designs 23(7) (2015) 305–320. doi:10.1002/jcd.21413, https://doi.org/10.1002/jcd.21413
3. S. Eberhard, F. Manners, and R. Mrazović. Additive triples of bijections, or the toroidal semiqueens problem. Journal of the European Mathematical Society 21(2) (2018) 441–463. doi:10.4171/jems/841, arXiv:1510.05987, https://arxiv.org/abs/1510.05987
4. M. Kwan. Almost all Steiner triple systems have perfect matchings. Proceedings of the London Mathematical Society (3) 121(6) (2020) 1468–1495. doi:10.1112/plms.12373, arXiv:1611.02246, https://arxiv.org/abs/1611.02246
5. S. Eberhard, F. Manners, and R. Mrazović. Transversals in quasirandom latin squares. Proceedings of the London Mathematical Society (3) 127(1) (2023) 84–115. doi:10.1112/plms.12538, arXiv:2209.02180, https://arxiv.org/abs/2209.02180
6. R. Montgomery. A proof of the Ryser–Brualdi–Stein conjecture for large even n. arXiv:2310.19779 (2023), https://arxiv.org/abs/2310.19779
7. R. Montgomery. Transversals in Latin squares. Surveys in Combinatorics 2024, London Mathematical Society Lecture Note Series 493, Cambridge University Press (2024) 131–158. doi:10.1017/9781009490559.006, arXiv:2406.19873, https://arxiv.org/abs/2406.19873 (survey written to accompany a talk at the 30th British Combinatorial Conference)
8. T. Dai, A. Divoux, and T. Kelly. Entropy bounds for perfect matchings in bipartite hypergraphs. The Electronic Journal of Combinatorics 33(2) (2026), article P2.20. doi:10.37236/14339, arXiv:2506.17652, https://arxiv.org/abs/2506.17652
9. A. A. Taranenko. Transversals in completely reducible multiary quasigroups and in multiary quasigroups of order 4. arXiv:1612.01797, https://arxiv.org/abs/1612.01797
10. A. A. Taranenko. Transversals, plexes, and multiplexes in iterated quasigroups. arXiv:1709.03071, https://arxiv.org/abs/1709.03071
11. A. A. Taranenko. Transversals, near transversals, and diagonals in iterated groups and quasigroups. arXiv:2006.03786, https://arxiv.org/abs/2006.03786
12. B. Child and I. M. Wanless. Multidimensional permanents of polystochastic matrices. arXiv:2004.14148, https://arxiv.org/abs/2004.14148
13. B. Child and I. M. Wanless. Latin hypercubes with restricted transversals. arXiv:2605.01813 (2026), https://arxiv.org/abs/2605.01813
14. A. L. Perezhogin, V. N. Potapov, and S. Yu. Vladimirov. Every latin hypercube of order 5 has transversals. Journal of Combinatorial Designs 32(11) (2024) 679–699. doi:10.1002/jcd.21954, arXiv:2311.14997, https://arxiv.org/abs/2311.14997
15. B. D. McKay, J. C. McLeod, and I. M. Wanless. The number of transversals in a Latin square. Designs, Codes and Cryptography 40(3) (2006) 269–284. doi:10.1007/s10623-006-0012-8, https://doi.org/10.1007/s10623-006-0012-8
16. I. M. Wanless. Transversals in Latin squares: a survey. Surveys in Combinatorics 2011, London Mathematical Society Lecture Note Series 392, Cambridge University Press (2011) 403–437. doi:10.1017/cbo9781139004114.010, https://doi.org/10.1017/cbo9781139004114.010
17. I. Vardi. Computational Recreations in Mathematica. Addison-Wesley, Redwood City, CA (1991). zbMATH: Zbl 0786.11002, https://zbmath.org/?q=an%3A0786.11002
18. H. J. Ryser. Neuere Probleme der Kombinatorik. In Vorträge über Kombinatorik, Oberwolfach, 24–29 Juli (1967) 69–91. Primary source of Ryser's odd-order transversal conjecture. No DOI exists for this 1967 Oberwolfach lecture-notes article; zbMATH review Zbl 0704.05007, https://zbmath.org/?q=an%3A0704.05007.