High-dimensional permutations and discrepancy

by · Jul 23, 2016 · 625 views ·

The Mathematics of Jiří Matoušek

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 largely start from a familiar phenomenon in the study of permutations and seek its high dimensional counterparts. Specifically we already have some progress on the following: The enumeration problem Birkhoff von-Neumann theorem and d-stochastic arrays Erdös-Szekeres theorem and monotone sub-sequences Discrepancy phenomena – this will be a major focus of my lecture Random generation Almost everything that I will be presenting is joint work with my ex-student Zur Luria.