Nir Lavee (HUJI) —  How Balanced Can Permutations Be?

Nir Lavee (HUJI) — How Balanced Can Permutations Be?

Nir Lavee (HUJI) — How Balanced Can Permutations Be?

Wednesday, July 31, 2024
  • Lecturer: Nir Lavee
  • Organizer: Chaim Even Zohar
  • Location: 814 Amado
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 ≤ 3, and every n that satisfies the necessary divisibility conditions. In contrast, we prove that for k ≥ 4, no such permutations exist, and in fact every n-element permutation is at least Ω(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.
Print to PDF