A permutation regularity lemma

MaRDI QIDQ819184zbMATH OpenFDO

Authors Joshua Cooper

Publication date 22 March 2006

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0405266, https://eudml.org/doc/125854, http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1r22.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

permutation quasirandomnessSzemerédi regularity lemma

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: We introduce a permutation analogue of the celebrated Szemeredi 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 sub-patterns of a permutation with an integral, and relate our results to permutation quasirandomness in a manner analogous to the graph-theoretic setting.

Recommendations

• A note on permutation regularity
• A note on permutation regularity
• On regularity lemmas and their algorithmic applications
• A viewpoint for permutations with a low density of patterns
• scientific article; zbMATH DE number 2086426

Cited in

(12)

• Patterns in random permutations
• A note on random \(k\)-dimensional posets
• scientific article; zbMATH DE number 7771747 (Why is no real title available?)
• A cycle lemma for permutation inversions
• Fast property testing and metrics for permutations
• Testing permutation properties through subpermutations
• On pattern-avoiding permutons
• A note on permutation regularity
• A note on permutation regularity
• On regularity lemmas and their algorithmic applications
• A tightness property of relatively smooth permutations
• Some remarks on the permutability of regular sequences

This page was built for publication: A permutation regularity lemma

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