Geodesic
A permutation regularity lemma
The electronic journal of combinatorics, Tome 13 (2006)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 sub-patterns of a permutation with an integral, and relate our results to permutation quasirandomness in a manner analogous to the graph-theoretic setting.
DOI : 10.37236/1048
Classification : 05D40, 05A05
Mots-clés : Szemerédi regularity lemma, permutation quasirandomness 
@article{10_37236_1048,
     author = {Joshua N. Cooper},
     title = {A permutation regularity lemma},
     journal = {The electronic journal of combinatorics},
     year = {2006},
     volume = {13},
     doi = {10.37236/1048},
     zbl = {1085.05065},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1048/}
}
TY  - JOUR
AU  - Joshua N. Cooper
TI  - A permutation regularity lemma
JO  - The electronic journal of combinatorics
PY  - 2006
VL  - 13
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1048/
DO  - 10.37236/1048
ID  - 10_37236_1048
ER  - 
%0 Journal Article
%A Joshua N. Cooper
%T A permutation regularity lemma
%J The electronic journal of combinatorics
%D 2006
%V 13
%U http://geodesic.mathdoc.fr/articles/10.37236/1048/
%R 10.37236/1048
%F 10_37236_1048
Joshua N. Cooper. A permutation regularity lemma. The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1048

Cité par Sources :