Nati Linial: High-Dimensional Permutations

Abstract: This talk starts from the realization that many of the basic combinatorial constructs that we use all the time are inherently one dimensional. Permutations are a case in point. As we know, a permutation is synonymous with a permutation matrix, namely an nxn array of zeros and ones in which every line (row or column) contains exactly one 1. This suggests that a two-dimensional permutation is an nxnxn array of zeros and ones where every line (row column or shaft) contains exactly one 1. It is not hard to see that a two dimensional permutation is synonymous with an order n Latin square. The d-dimensional notion suggests itself naturally. Many questions arise, some we know how to solve and some are still open. For example:
1. How many d-dimensional permutations are there?
2. What about a d-dimensional analog of the Birkhoff von-Neumann Theorem?
3. Likewise for Erdos-Szekeres.
4. What do random d-dimensional permutations look like? (Here we still have mostly questions and intriguing conjectures).

Work done with my PhD students Zur Luria (presently postdoc at ETH) and Michael Simkin.