×

zbMATH — the first resource for mathematics

Geometry of permutation limits. (English) Zbl 1449.60010
This article concerns permutons (a measure on a square with uniform marginal distributions) and permuton processes (a process \(X\) with continuous sample paths such that each \(X(t)\) is uniformly distributed on some fixed interval). In the graph of the symmetric group \(\mathfrak{S}_n\), a sorting network is a geodesic from the permutation \((1 2 3 \dots n)\) to \((n (n - 1) (n - 2) \dots 1)\). This article is a hopeful step towards resolving the Archimedean path conjecture of O. Angel et al. [Adv. Math. 215, No. 2, 839–868 (2007; Zbl 1132.60008)], which states that as \(n \to \infty\), the random sorting network process on \(\mathfrak{S}_n\) converges in probability to the “Archimedean process” \[ \mathcal{A}(t) = \cos (\pi t) \mathbb{A}_x + \sin (\pi t) \mathbb{A}_y, t \in [0,1]\] for an appropriate random variable \((\mathbb{A}_x, \mathbb{A}_y)\) on the plane, defined in terms of an “Archimedean measure”.
The primary results of this article are:
A process is a permuton process if and only if it is the limit of a sequence of permutation-valued processes.
Among permuton processes \(X(t)\), \(0 \leq t \leq 1\), on the square \([-1, 1]\), such that \(X(1) = - X(0)\), there is a unique process with minimal Dirichlet energy, and it is Archimedean.
Given a permuton-valued path from the identity permuton (of support \(\{ (x, x) : x \in [-1, 1] \}\)) to the reverse permuton (of support \(\{ (x, -x) : x \in [-1, 1] \}\)), the Dirichlet energy (via the Wasserstein metric) of the path is bounded below by the energy of the Archimedean path, that minimum achieved only by the Archimedean path.
However, there is a function of permutons which, if minimized by a nontrivial permuton, is minimized by at least four distinct permutons.
There is a qualitative discussion in which it is asserted that second statement above and the results of M. Kotowski [Limits of random permuton processes and large deviations of the interchange process. Toronto: University of Toronto (PhD Thesis) (2016)] together establish the Archimedean path conjecture for “relaxed” random sorting networks.

MSC:
60C05 Combinatorial probability
05E18 Group actions on combinatorial structures
60G57 Random measures
PDF BibTeX XML Cite
Full Text: DOI