A note on permutation regularity

详细信息    查看全文

• 作者：Carlos Hoppen ; Yoshiharu Kohayakawa ; Rudini M. Sampaio
• 关键词：Combinatorics of permutations ; Regularity lemma ; Patterns ; Discrepancy ; Convergence for permutation sequences
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 出版时间：December, 2012
• 年：2012
• 卷：160
• 期：18
• 页码：2716-2727
• 全文大小：259 K

文摘

The existence of a small partition of a combinatorial structure into random-like subparts, a so-called regular partition, has proven to be very useful in the study of extremal problems, and has deep algorithmic consequences. The main result in this direction is the Szemer¨¦di Regularity Lemma in graph theory. In this note, we are concerned with regularity in permutations: we show that every permutation of a sufficiently large set has a regular partition into a small number of intervals. This refines the partition given by Cooper (2006) , which required an additional non-interval exceptional class. We also introduce a distance between permutations that plays an important r?le in the study of convergence of a permutation sequence.