An upper bound on the number of high-dimensional permutations |
| |
Authors: | Nathan Linial Zur Luria |
| |
Affiliation: | 1. Department of Computer Science, Hebrew University, Jerusalem, 91904, Israel
|
| |
Abstract: | 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 n×n×...×n=[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 ∈ [n] for all j ≠ 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 $$left( {(1 + o(1))frac{n} {{e^d }}} right)^{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 Brégman’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 Brégman’s theorem. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|