How Balanced Can Permutations Be?

MaRDI QIDQ6441998zbMATH OpenFDO

Authors Nir Lavee, Nathan Linial

Publication date 29 June 2023

Abstract: A permutation $piinmathbb{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 $kle3$, and every $n$ that satisfies the necessary divisibility conditions. In contrast, we prove that for $kge4$, no such permutations exist. In fact, we show that in the case $kge4$, every $n$-element permutation is at least $Omeg{a}_n(n^{k-1})$ far from being $k$-balanced. This lower bound is matched for $k=4$, by a construction based on the ErdH{o}s-Szekeres permutation.

This page was built for publication: How Balanced Can Permutations Be?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6441998)