A note on permutation regularity
| Contribuinte(s) |
UNIVERSIDADE DE SÃO PAULO |
|---|---|
| Data(s) |
09/08/2013
09/08/2013
01/12/2012
|
| Resumo |
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 Szemeredi 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) [10], which required an additional non-interval exceptional class. We also introduce a distance between permutations that plays an important role in the study of convergence of a permutation sequence. (C) 2011 Elsevier B.V. All rights reserved. FAPERGS FAPERGS [Proc. 10/0388-2] FAPESP [Proc. 2007/56496-3] FAPESP CNPq CNPq [Proc. 484154/2010-9, Proc. 308509/2007-2] FUNCAP FUNCAP [Proc. 07.013.00/09] |
| Identificador |
DISCRETE APPLIED MATHEMATICS, AMSTERDAM, v. 160, n. 18, Special Issue, supl. 1, Part 2, pp. 2716-2727, DEC, 2012 0166-218X http://www.producao.usp.br/handle/BDPI/32532 10.1016/j.dam.2011.06.002 |
| Idioma(s) |
eng |
| Publicador |
ELSEVIER SCIENCE BV AMSTERDAM |
| Relação |
DISCRETE APPLIED MATHEMATICS |
| Direitos |
restrictedAccess Copyright ELSEVIER SCIENCE BV |
| Palavras-Chave | #COMBINATORICS OF PERMUTATIONS #REGULARITY LEMMA #PATTERNS #DISCREPANCY #CONVERGENCE FOR PERMUTATION SEQUENCES #ONE-SIDED ERROR #GRAPH PROPERTIES #SEQUENCES #MATRICES #MATHEMATICS, APPLIED |
| Tipo |
article original article publishedVersion |
