Geodesic
A permutation regularity lemma
The electronic journal of combinatorics, Tome 13 (2006)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv EuDML
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 
Joshua N. Cooper. A permutation regularity lemma. The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1048
@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

Cité par Sources :