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 renowned Szemerédi Regularity Lemma [Szemerédi, E., Regular partitions of graphs, Colloques Internationaux C.N.R.S. No: 260 – Problèmes Combinatoires et Théorie des Graphes, Orsay (1976), 399–401] 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 partitioning given by Cooper [Cooper, J., A permutation regularity lemma, The Electronic Journal of Combinatorics 13 (2006), 20pp.], which required an additional non-interval exceptional class. We also introduce a distance between permutations that plays an important role in the study of convergence of a permutation sequence.