Combinatorics Seminar
When: Sunday, November 6, 10am
Where: Schreiber 309
Speaker: Nathan Linial, Hebrew University
Title: What are high-dimensional permutations? How many
are there?
Abstract:
As we know, a permutation can be represented by a permutation
matrix, namely an nxn array in which every entry is zero or one
where every line contains exactly one 1-entry. A "line" is a row
or a column. If this is a "one-dimensional permutation", it is
very suggestive how to define a d-dimensional permutation. It is
an nxnx....xn array (d+1 factors) of zero and one entries where
every line (now there are d+1 types of lines) contains exactly
one 1-entry. We know a lot, of course, about permutations and it
is very interesting to seek high-dimensional counterparts of
these facts. In particular there are n! permutations and we wish
to know the number of d-dimensional permutations. The case d=2 is
an old subject, since a 2-dimensional permutation is synonymous
with a Latin square, and there is a reasonably good asymptotic
estimate for the number of Latin squares.
We get an upper bound on the number of d-dimensional permutations.
Our proof is based on the entropy method.
Joint work with Zur Luria.