Source-linked AI summary
Limits of permutation sequences
Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo Moreira, Balazs Rath, Rudini Menezes Sampaio
TL;DR
The paper addresses how to define and represent limits of permutation sequences whose fixed subpermutation densities converge. It introduces limit permutations and an associated random-permutation model, proving existence, realizability, and almost-everywhere uniqueness, while characterizing convergence metrically.
Problem
The paper seeks a natural limit object and convergence theory for permutation sequences, especially when their lengths tend to infinity.
Method
The paper models limits as measurable families of cumulative distribution functions, equivalently as probability distributions or regular conditional distribution functions, and uses a rectangular metric and random permutations.
Results
Every convergent sequence with lengths tending to infinity has a limit permutation, every limit permutation is realizable, and shared limits are equivalent exactly when their cdf restrictions differ on a null set.
Takeaways & Limitations
The theory provides a well-behaved completion framework in which convergence is equivalent to being Cauchy under d□ and finite permutations are dense after almost-everywhere identification.
Takeaways & Limitations
The main limit theorem assumes |σn| tends to infinity; when the lengths have a bounded subsequence, a convergent sequence is eventually constant.
Abstract
from arXiv · showhide
A permutation sequence is said to be convergent if the density of occurrences of every fixed permutation 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 \to [0,1]$ with the additional properties that, for every fixed $x \in [0,1]$, the restriction $Z(x,\cdot)$ is a cumulative distribution function and, for every $y \in [0,1]$, the restriction $Z(\cdot,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.
1. Introduction
The paper develops convergence and limit theory for permutation sequences, paralleling graph-limit ideas through subpermutation densities. It introduces limit permutations, establishes their existence and representability, and characterizes uniqueness and metric convergence.
- 1. Introduction: Permutation-sequence convergence is defined by convergence of the density of every fixed subpermutation.The paper develops this notion for finite permutations represented on [n].
- 1. Introduction: The paper focuses on sequences whose lengths tend to infinity, because convergent sequences with bounded lengths are eventually constant.For unbounded lengths, the natural limit object is a family of cumulative distribution functions.
- 1. Introduction: Limit permutations can be represented through regular conditional distribution functions or equivalent probability distributions with uniform marginals.The function Z(x,·) is interpreted as the conditional distribution function of Y given X=x.
- 1. Introduction: The framework also supports random-permutation models and motivates applications to property testing, where properties can be estimated from constant-size random substructures.The introduction places the theory within broader work on graph limits and testing combinatorial structures.
- 1. Introduction: Every convergent permutation sequence with lengths tending to infinity has a limit permutation, and every limit permutation is attained by some convergent permutation sequence.This establishes both existence and converse realizability of the proposed limit objects.
- 1. Introduction: Two limit permutations describe the same convergent sequence exactly when their defining cdf restrictions differ only on a set of x-values of Lebesgue measure zero.Thus the representation is unique up to the stated almost-everywhere equivalence, and unique as a probability distribution or random variable.
- 1. Introduction: The rectangular metric d□ characterizes convergence: a permutation sequence converges exactly when it is Cauchy in that metric.After identifying almost-everywhere-equal limit permutations, the enlarged metric space is compact and contains finite permutations densely.
2. Preliminaries
The preliminaries develop the probability-measure framework underlying limit permutations, including weak convergence on the unit square and the correspondence between uniform-marginal random variables and limit permutations. They also establish basic convergence facts for permutation sequences.
- Probability distributions: A joint distribution function F(x,y) records the probability that a unit-square random variable lies in [0,x] × [0,y].Its marginal distributions are obtained as F(x,1) and F(1,y).
- Probability distributions: Uniform marginals are characterized by F(x,1)=x and F(1,y)=y for all x,y ∈ [0,1].These are the marginal conditions required for random variables associated with limit permutations.
- Weak convergence: With uniform marginals, weak convergence is linked to pointwise convergence of joint distribution functions because rectangle boundaries have probability zero.The unit-square setting supplies the continuity-set condition needed for this conclusion.
- Weak convergence: Weak convergence of joint distributions implies weak convergence of their marginal distributions.In particular, weak limits preserve uniform marginals when every approximating pair has uniform marginals.
- Regular conditional probabilities: A random variable with uniform coordinates determines a limit permutation through the regular conditional distribution of Y given X, and conversely.The correspondence is essentially one-to-one, with equality understood almost surely.
- Permutation convergence: Every permutation sequence has a convergent subsequence, while a convergent sequence whose lengths do not tend to infinity is eventually constant.These facts separate the finite-length case from the asymptotic regime studied through limit permutations.
3. Z-random permutations and subpermutation densities
This section constructs random permutations from finite permutations and limit permutations, and relates their distributions to subpermutation densities. It also introduces a finite-permutation representation whose associated limit permutation approximates the finite object’s densities.
- Subpermutation densities: The paper defines the density t(τ,Z) of a fixed permutation τ in a limit permutation Z using the corresponding random-permutation model.This places finite and limit permutations in a common probabilistic framework.
- Random subpermutations: A random subpermutation σ(k,π) is formed by sampling k positions from π and recording the relative order of their values.Its distribution exactly encodes subpermutation densities: P(σ(k,π)=τ)=t(τ,π).
- Z-random permutations: A Z-random permutation samples i.i.d. pairs (X_i,Y_i) from the distribution associated with Z and ranks their horizontal and vertical coordinates.The resulting permutation is σ(n,Z)=S ◦ R^-1.
- Z-random permutations: The Z-random construction is well-defined with probability one because independent uniform coordinates have no repeated values.An equivalent construction samples X_i uniformly and then samples each Y_i from the conditional distribution induced by Z(X_i,·).
- Finite-to-limit representation: Each finite permutation σ is assigned a limit permutation Z_σ whose associated random coordinates reproduce the permutation’s grid structure.The construction uses the density f_σ(x,y)=n · 1[σ(⌈n·x⌉)=⌈n·y⌉], and the resulting coordinates have uniform marginals.
4. Rectangular distance
The paper introduces rectangular distance for permutations and limit permutations, connects the two through the representation Zσ, and shows that large random subpermutations approximate their limit objects.
- Sampling approximation: A limit permutation can be recovered from a sufficiently large random subpermutation with small rectangular-distance error, with high probability.The corresponding finite-permutation statement provides an approximation useful for characterizing testability.
- Quasi-randomness: Low-discrepancy permutations are called quasi-random, and discrepancy satisfies D(σ) = n · d□(σ, Zu) relative to the uniform limit permutation.This links the normalized distance to the earlier discrepancy measure and interprets it as a measure of permutation randomness.
- Distance definitions: Rectangular distance is defined for both finite permutations and limit permutations using discrepancies over axis-aligned rectangles.For limit permutations, the distance compares probabilities assigned to corresponding rectangles by their associated random variables.
- Equivalent formulations: The paper also establishes equivalences among rectangular, supremum, and joint-distribution formulations of equality for limit permutations.In particular, d□(Z1, Z2) = 0 is equivalent to equality of the associated distribution functions.
- Connection between spaces: The identity d□(σ, Z) := d□(Zσ, Z) embeds a finite permutation into the limit-permutation metric space.For finite permutations, d□(σ1, σ2) equals d□(Zσ1, Zσ2), extending the distance to permutations of different lengths.
5. Limits of permutation sequences
This section proves that the three convergence notions for limit permutations are equivalent and uses that result to characterize limits of permutation sequences. It establishes existence, random generation, and almost-everywhere uniqueness of these limits.
- Uniqueness: All subpermutation densities determine the associated probability distribution of a limit permutation.The proof recovers the joint distribution function from the expected empirical functions constructed from random subpermutations.
- Equivalent convergence notions: Weak convergence, rectangular-distance convergence, and convergence of all subpermutation densities are equivalent for limit permutations.These are the three notions defined in the section and unified by Lemma 5.3.
- Existence of limits: Every convergent permutation sequence with lengths tending to infinity converges to a limit permutation.The proof extracts a subsequential distributional limit, constructs its limit permutation, and then uses convergence of the original densities to identify the full-sequence limit.
- Random permutation model: Every limit permutation generates a jointly defined random sequence of permutations that almost surely converges to it.The construction samples i.i.d. points from the associated distribution and takes relative vertical orders according to ordered horizontal coordinates.
- Uniqueness of sequence limits: If one permutation sequence converges to two limit permutations, their conditional-distribution functions agree for almost every first coordinate.Thus the limit is unique up to the paper’s almost-everywhere equivalence.
Appendix A. Proof of Lemma 2.2
The appendix constructs the conditional-distribution-function representation of a limit permutation and proves its defining properties and almost-everywhere uniqueness using conditional expectation.
- Probabilistic foundation: The appendix relies on existence and almost-sure uniqueness of conditional expectation with respect to the sigma-algebra generated by X.This theorem provides the foundational measurable object used throughout the construction.
- Conditional-distribution construction: Conditional expectation supplies measurable versions of the conditional distribution of Y given X.The construction begins with rational threshold values and then extends the resulting monotone functions to all y.
- Limit-permutation properties: The constructed function Z is measurable, and each restriction Z(x, ·) is a cumulative distribution function.Monotonicity and right continuity are obtained on a full-measure set and extended across the unit interval.
- Mass condition: Uniformity of Y implies the mass condition required in the definition of a limit permutation.The proof applies the conditional-expectation identity and monotone convergence to establish the condition.
- Almost-everywhere uniqueness: Any other limit permutation satisfying the same conditional-expectation identity agrees with Z for almost every x.Agreement first holds on rational thresholds and then extends to every y by right continuity.