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.

Date: 

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

Location: 

Manchester Building (Hall 2), Hebrew University Jerusalem