Colloquium: Nati Linial (Hebrew University) "Higher dimensional permutations"

This is part of our ongoing effort to develop what we call "High-dimensional combinatorics". We equate a permutation with its permutation matrix, namely an nxn array of zeros and ones in which every line (row or column) contains exactly one 1. In analogy, a two-dimensional permutation is an nxnxn array of zeros and ones in which every line (row, column or shaft) contains exactly one 1. It is not hard to see that a two-dimensional permutation is synonymous with a Latin square. It should be clear what a d-dimensional permutation is, and those are still very partially understood. We have already made good progress on several aspects of this field. We mostly start from a familiar phenomenon in the study of permutations and seek its high dimensional counterparts. Specifically we consider:
-The enumeration problem
-Birkhoff von-Neumann theorem and d-stochastic arrays
-Erdos-Szekeres theorem and monotone sub-sequences
-Discrepancy phenomena
-Problems related to communication complexity
-Random generation
These results were obtained in collaboration with my students and ex-students: Zur Luria, Michael Simkin and Adi Shraibman.


Thu, 10/03/2016 - 15:30 to 16:30


Manchester Building (Hall 2), Hebrew University Jerusalem