HD-Combinatorics: Nati Linial, "High-dimensional permutations"

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...

Date: 

Mon, 23/10/2017 - 14:00 to 16:00

Location: 

Israel Institute for Advanced Studies (Feldman building, Givat Ram), Eilat Hall