How Balanced Can Permutations Be?
Open Access
- 2 January 2025
- journal article
- research article
- Published by Springer Nature in Combinatorica
- Vol. 45 (1) , 1-31
Abstract
A permutation $$\pi \in \mathbb {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$$ , and every n that satisfies the necessary divisibility conditions. In contrast, we prove that for $$k \ge 4$$ , no such permutations exist. In fact, we show that in the case $$k \ge 4$$ , every n-element permutation is at least $$\Omega _n(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.
Keywords
All Related Versions
Funding Information
- Hebrew University of Jerusalem
This publication has 16 references indexed in Scilit:
- Patterns in Random PermutationsCombinatorica, 2020
- How unproportional must a graph be?European Journal of Combinatorics, 2018
- Quasirandom permutations are characterized by 4-point densitiesGeometric and Functional Analysis, 2013
- Limits of permutation sequencesJournal of Combinatorial Theory, Series B, 2013
- Quasirandom permutationsJournal of Combinatorial Theory, Series A, 2004
- The patterns of permutationsDiscrete Mathematics, 2002
- Probabilistic construction of proportional graphsRandom Structures & Algorithms, 1992
- Quasi-random graphsCombinatorica, 1989
- Pseudo-Random Graphs1987
- The inducibility of graphsJournal of Combinatorial Theory, Series B, 1975