The asymptotic enumeration conjecture for high-dimensional permutations

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.

Sources & referencesView supporting material

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.