Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-17T06:13:48.008Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Brownian separable permuton

Part of: Combinatorics Combinatorial probability

Published online by Cambridge University Press:  24 October 2019

Mickaël Maazoun
Mickaël Maazoun*
Affiliation:
Université de Lyon – École Normale Supérieure de Lyon – UMPA UMR 5669 CNRS, 46 allée d’Italie, 69364 Lyon, France
*
Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The Brownian separable permuton is a random probability measure on the unit square, which was introduced by Bassino, Bouvel, Féray, Gerin and Pierrot (2016) as the scaling limit of the diagram of the uniform separable permutation as size grows to infinity. We show that, almost surely, the permuton is the pushforward of the Lebesgue measure on the graph of a random measure-preserving function associated to a Brownian excursion whose strict local minima are decorated with independent and identically distributed signs. As a consequence, its support is almost surely totally disconnected, has Hausdorff dimension one, and enjoys self-similarity properties inherited from those of the Brownian excursion. The density function of the averaged permuton is computed and a connection with the shuffling of the Brownian continuum random tree is explored.

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 05A05: Permutations, words, matrices
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 2 , March 2020 , pp. 241 - 266
Copyright
© Cambridge University Press 2019

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Albenque, M. and Goldschmidt, C. (2015) The Brownian Continuum Random Tree as the unique solution to a fixed point equation. Electron. Commun. Probab. 20 61.CrossRefGoogle Scholar
Aldous, D. (1993) The Continuum Random Tree III. Ann. Probab. 21 248–289.CrossRefGoogle Scholar
Aldous, D. (1994) Recursive self-similarity for random trees, random triangulations and Brownian excursion. Ann. Probab. 22 527–545.CrossRefGoogle Scholar
Avis, D. and Newborn, M. (1981) On pop-stacks in series. Utilitas Math. 19 129–140.Google Scholar
Bassino, F., Bouvel, M., Féray, V., Gerin, L. and Pierrot, A. (2018) The Brownian limit of separable permutations. Ann. Probab. 46 2134–2189.CrossRefGoogle Scholar
Bassino, F., Bouvel, M., Féray, V., Gerin, L., Maazoun, M. and Pierrot, A. (2019) Universal limits of substitution-closed permutation classes. J. Eur. Math. Soc.Google Scholar
Bassino, F., Bouvel, M., Féray, V., Gerin, L., Maazoun, M. and Pierrot, A. (2019) Scaling limits of permutation classes with a finite specification: A dichotomy. arXiv:1903.07522Google Scholar
Bertoin, J. and Pitman, J. (1994) Path transformations connecting Brownian bridge, excursion and meander. Bull. Sci. Math. 118 147–166.Google Scholar
Bona, M. (2004) Combinatorics of Permutations, CRC Press.CrossRefGoogle Scholar
Borodin, A. N. and Salminen, P. (2002) Handbook of Brownian Motion: Facts and Formulae, second edition, Probability and its Applications, Birkhäuser.CrossRefGoogle Scholar
Bose, P., Buss, J. F. and Lubiw, A. (1993) Pattern matching for permutations. In Algorithms and Data Structures: Third Workshop: WADS ’93 (F. Dehne et al., eds), Springer, 200–209.Google Scholar
Dokos, T. and Pak, I. (2014) The expected shape of random doubly alternating Baxter permutations. Online J. Anal. Combin . 9 1–12.Google Scholar
Duquesne, T. (2006) The coding of compact real trees by real valued functions. arXiv:math/0604106Google Scholar
Ghys, E. (2017) A Singular Mathematical Promenade, ENS Éditions.Google Scholar
Hoppen, C., Kohayakawa, Y., Moreira, C. G., Ráth, B. and Sampaio, R. M. (2013) Limits of permutation sequences. J. Combin. Theory Ser. B 103 93–113.CrossRefGoogle Scholar
Kingman, J. F. C. (1993) Poisson Processes, Vol. 3 of Oxford Studies in Probability, Oxford University Press.Google Scholar
Le Gall, J.-F. (2005) Random trees and applications. Probab. Surveys 2 245–311.CrossRefGoogle Scholar
Ouchterlony, E. (2005) On young tableau involutions and patterns in permutations. Linköping Studies in Science and Technology. Dissertations No. 993, Linköpings universitet, Sweden.Google Scholar
Perman, M. and Wellner, J. A. (2014) An excursion approach to maxima of the Brownian bridge. Stoch. Process. Appl. 124 3106–3120.CrossRefGoogle ScholarPubMed
Shapiro, L. and Stephens, A. B. (1991) Bootstrap percolation, the Schröder numbers, and the N-kings problem. SIAM J. Discrete Math. 4 275–280.CrossRefGoogle Scholar