Limits of permutation sequences

Author(s)

Hoppen, Carlos ^[1] ; Kohayakawa, Yoshiharu ^[2] ; Moreira, Carlos Gustavo ^[3] ; Rath, Balazs ^[4] ; Sampaioe, Rudini Menezes ^[5]

Affiliation

^[1] Univ Fed Rio Grande do Sul, Inst Matemat, BR-91509900 Porto Alegre, RS - Brazil

^[2] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil

^[3] IMPA, BR-22460320 Rio De Janeiro, RJ - Brazil

^[4] Univ British Columbia, Dept Math, Vancouver, BC V6T 1Z2 - Canada

^[5] Univ Fed Ceara, Dept Comp, Ctr Ciencias, BR-60451760 Fortaleza, Ceara - Brazil

• Document type: Journal article
• Source: JOURNAL OF COMBINATORIAL THEORY SERIES B; v. 103, n. 1, p. 93-113, JAN 2013.
• Web of Science Citations: 21

Abstract

A permutation sequence (sigma(n))(n epsilon N) is said to be convergent if, for every fixed permutation tau, the density of occurrences of tau in the elements of the sequence converges. We prove that such a convergent sequence has a natural limit object, namely a Lebesgue measurable function Z : {[}0, 1](2) -> {[}0,1] with the additional properties that, for every fixed x epsilon {[}0, 1], the restriction Z(x, .) is a cumulative distribution function and, for every y epsilon {[}0, 1], the restriction Z(., y) satisfies a ``mass{''} condition. This limit process is well-behaved: every function in the class of limit objects is a limit of some permutation sequence, and two of these functions are limits of the same sequence if and only if they are equal almost everywhere. An ingredient in the proofs is a new model of random permutations, which generalizes previous models and might be interesting for its own sake. (C) 2012 Elsevier Inc. All rights reserved. (AU)