A Permutation Regularity Lemma
| dc.creator | Cooper, Joshua N. | |
| dc.date | 2004-05-14 | |
| dc.date | 2006-02-28 | |
| dc.date.accessioned | 2026-07-07T06:36:46Z | |
| dc.date.available | 2026-07-07T06:36:46Z | |
| dc.description | 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. | |
| dc.description | Minor corrections, to appear in Electronic Journal of Combinatorics | |
| dc.identifier | https://arxiv.org/abs/math/0405266 | |
| dc.identifier | http://arxiv.org/abs/math/0405266 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/100195 | |
| dc.subject | Combinatorics | |
| dc.subject | 05D99 | |
| dc.title | A Permutation Regularity Lemma | |
| dc.type | text |