The asymptotic enumeration conjecture for high-dimensional permutations

About 15 years old · traced to

For positive integers dd and nn, let Sd,nS_{d,n} denote the set of dd-dimensional permutations of order nn: equivalently, the [n]d[n]^d arrays with entries in [n][n] in which every line contains each element of [n][n] exactly once. Thus ∣Sd,n∣|S_{d,n}| is the number of dd-dimensional permutations of order nn.

Asymptotic enumeration conjecture.

∣Sd,n∣=((1+o(1))ned)nd.|S_{d,n}|=\left((1+o(1))\frac{n}{e^d}\right)^{n^d}.

For d=1d=1 this follows from Stirling's formula, and for d=2d=2 it is the known asymptotic estimate for Latin squares. The paper's main result gives the corresponding upper bound, while the complementary lower bound remains open; the displayed equality is therefore an open conjecture.

References

Primary source

Nathan Linial and Zur Luria, “An upper bound on the number of high-dimensional permutations”, arXiv:1106.0649 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.