A permutation regularity lemma (Q819184)

Summary: We introduce a permutation analogue of the celebrated Szemerédi regularity lemma, and derive a number of consequences. This tool allows us to provide a structural description of permutations which avoid a specified pattern, a result that permutations which scatter small intervals contain all possible patterns of a given size, a proof that every permutation avoiding a specified pattern has a nearly monotone linear-sized subset, and a ``thin deletion'' result. We also show how one can count subpatterns of a permutation with an integral, and relate our results to permutation quasirandomness in a manner analogous to the graph-theoretic setting.