Talk information

Date: Sunday, June 15, 2025
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Nir Lavee (Hebrew University)
Title: How balanced can permutations be?

Abstract:

An $n$-element permutation is called $k$-balanced if every $k$-element permutation occurs in it equally often, through order-isomorphism. We explicitly construct $k$-balanced permutations for $k \leq 3$, and every $n$ that satisfies the necessary divisibility conditions. In contrast, we prove that for $k \geq 4$, no such permutations exist, and in fact every $n$-element permutation is at least $\Omega(n^{k−1})$ far from being $k$-balanced. This lower bound is matched for $k = 4$, by a construction based on the Erdős-Szekeres permutation. Joint work with Gal Beniamini and Nati Linial.