A note on permutation regularity

The existence of a small partition of a combinatorial structure into random-like subparts, a so-called regular partition, has proven to be very useful in the study of extremal problems, and has deep algorithmic consequences. The main result in this direction is the Szemerédi Regularity Lemma in graph theory. In this note, we are concerned with regularity in permutations: we show that every permutation of a sufficiently large set has a regular partition into a small number of intervals. This refines the partition given by Cooper (2006) [10], which required an additional non-interval exceptional class. We also introduce a distance between permutations that plays an important rôle in the study of convergence of a permutation sequence.

► We address the concept of regularity for permutations. ► For large permutations, we give regular partitions with no exceptional class. ► We introduce a permutation distance based on the concept of quasi-randomness. ► This distance is connected to the convergence of permutation sequences.