Combinatorica Computational Mathematics

How Balanced Can Permutations Be?

Gal Beniamini, Nir Lavee, Nati Linial
Springer Nature · 2025-01-02 · DOI 10.1007/s00493-024-00127-x

Abstract

Abstract A permutation $$\pi \in \mathbb {S}_n$$ π ∈ S n is k - balanced if every permutation of order k occurs in $$\pi $$ π equally often, through order-isomorphism. In this paper, we explicitly construct k -balanced permutations for $$k \le 3$$ k ≤ 3 , and every n that satisfies the necessary divisibility conditions. In contrast, we prove that for $$k \ge 4$$ k ≥ 4 , no such permutations exist. In fact, we show that in the case $$k \ge 4$$ k ≥ 4 , every n -element permutation is at least $$\Omega _n(n^{k-1})$$ Ω n ( n k - 1 ) far from being k -balanced. This lower bound is matched for $$k=4$$ k = 4 , by a construction based on the Erdős–Szekeres permutation.

Read at publisher →