A permutation regularity lemma (Q819184)

From MaRDI portal
Revision as of 01:17, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
A permutation regularity lemma
scientific article

    Statements

    A permutation regularity lemma (English)
    0 references
    0 references
    22 March 2006
    0 references
    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.
    0 references
    Szemerédi regularity lemma
    0 references
    permutation quasirandomness
    0 references

    Identifiers