This is a survey talk about one of the main parts of what we call high-dimensional combinatorics. We start by equating a permutation with a permutation matrix. Namely, an nxn array of zeros and ones where every line (=row or column) contains exactly one 1. In general, a d-dimensional permutation is an array [n]x[n]x....x[n] (d+1 factors) of zeros and ones in which every line (now there are d+1 types of lines) contains exactly one 1. Many questions suggest themselves, some of which we have already solved, but many others are still wide opne. Here are a few examples:
--How many are they? I will present a natural conjecture that suggests itself by observing the cases d=1,2. With Zur Luria we have established it as an upper bound, but the matching lower bound is still unknown.
--The Erdos-Szekeres theorem says that every permutation in S_n has a monotone subsequence of length sqrt n. With Michael Simkin we have derived the analogous high-dimensional result.
--Do there exist HD permutations with low discrepancy? Is this what happens typically? Joint work with Luria gives some results in this direction.
--Perhaps the most pressing set of questions on which we still know too little concerns the typical structure of HD permutations.
--If time permits I will talk about random HD permutations, perhaps mention work with Maya Dotan on generating large one-factorizations. There is more...