An upper bound on the number of high-dimensional permutations

作者：Linial Nathan^*; Luria Zur

来源：Combinatorica, 2014, 34(4): 471-486.

DOI：10.1007/s00493-011-2842-8

What is the higher-dimensional analog of a permutation? If we think of a permutation as given by a permutation matrix, then the following definition suggests itself: A d-dimensional permutation of order n is an nxnx...xn=[n] (d+1) array of zeros and ones in which every line contains a unique 1 entry. A line here is a set of entries of the form {(x (1),...,x (i-1),y,x (i+1),...,x (d+1))|n >= y >= 1} for some index d+1 >= i >= 1 and some choice of x(j) epsilon [n] for all j not equal i. It is easy to observe that a one-dimensional permutation is simply a permutation matrix and that a two-dimensional permutation is synonymous with an order-n Latin square. We seek an estimate for the number of d-dimensional permutations. Our main result is the following upper bound on their number
((1+0(1))n/ed)n(d).
We tend to believe that this is actually the correct number, but the problem of proving the complementary lower bound remains open. Our main tool is an adaptation of Bregman's [1] proof of the Minc conjecture on permanents. More concretely, our approach is very close in spirit to Schrijver's [11] and Radhakrishnan's [10] proofs of Bregman's theorem.

• 出版日期2014-8