Document Open Access Logo

Scaling and Local Limits of Baxter Permutations Through Coalescent-Walk Processes

Authors Jacopo Borga , Mickaël Maazoun

PDF
Thumbnail PDF

File

LIPIcs.AofA.2020.7.pdf
  • Filesize: 1.01 MB
  • 18 pages

Document Identifiers

Author Details

Jacopo Borga
  • Institut für Mathematik, Universität Zürich, Switzerland
Mickaël Maazoun
  • Université de Lyon, ENS de Lyon, Unité de Mathématiques Pures et Appliquées, France

Acknowledgements

Thanks to Mathilde Bouvel, Valentin Féray and Grégory Miermont for their dedicated supervision and enlightening discussions. Thanks to Nicolas Bonichon, Emmanuel Jacob, Jason Miller, Kilian Raschel, Olivier Raymond, Vitali Wachtel, for enriching discussions and pointers.

Cite AsGet BibTex

Jacopo Borga and Mickaël Maazoun. Scaling and Local Limits of Baxter Permutations Through Coalescent-Walk Processes. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.AofA.2020.7

Abstract

Baxter permutations, plane bipolar orientations, and a specific family of walks in the non-negative quadrant are well-known to be related to each other through several bijections. We introduce a further new family of discrete objects, called coalescent-walk processes, that are fundamental for our results. We relate these new objects with the other previously mentioned families introducing some new bijections. We prove joint Benjamini - Schramm convergence (both in the annealed and quenched sense) for uniform objects in the four families. Furthermore, we explicitly construct a new fractal random measure of the unit square, called the coalescent Baxter permuton and we show that it is the scaling limit (in the permuton sense) of uniform Baxter permutations. To prove the latter result, we study the scaling limit of the associated random coalescent-walk processes. We show that they converge in law to a continuous random coalescent-walk process encoded by a perturbed version of the Tanaka stochastic differential equation. This result has connections (to be explored in future projects) with the results of Gwynne, Holden, Sun (2016) on scaling limits (in the Peanosphere topology) of plane bipolar triangulations. We further prove some results that relate the limiting objects of the four families to each other, both in the local and scaling limit case.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Probability and statistics
  • Mathematics of computing → Permutations and combinations
Keywords
  • Local and scaling limits
  • permutations
  • planar maps
  • random walks in cones

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

  • A full version of this extended abstract will be submitted later to another journal.

References

  1. F. Bassino, M. Bouvel, V. Féray, L. Gerin, M. Maazoun, and A. Pierrot. Universal limits of substitution-closed permutation classes. Journal of the European Mathematical Society, to appear, 2019. Google Scholar
  2. F. Bassino, M. Bouvel, V. Féray, L. Gerin, and A. Pierrot. The Brownian limit of separable permutations. The Annals of Probability, 46(4):2134-2189, 2018. Google Scholar
  3. G. Baxter. On fixed points of the composite of commuting functions. Proc. Amer. Math. Soc., 15:851-855, 1964. URL: https://doi.org/10.2307/2034894.
  4. I. Benjamini and O. Schramm. Recurrence of distributional limits of finite planar graphs. Electron. J. Probab., 6:no. 23, 13, 2001. URL: https://doi.org/10.1214/EJP.v6-96.
  5. N. Bonichon, M. Bousquet-Mélou, and É. Fusy. Baxter permutations and plane bipolar orientations. Sém. Lothar. Combin., 61A:Art. B61Ah, 29, 2009/11. Google Scholar
  6. J. Borga. Local convergence for permutations and local limits for uniform ρ-avoiding permutations with |ρ |=3. Probability Theory and Related Fields, 176(1):449-531, 2020. URL: https://doi.org/10.1007/s00440-019-00922-4.
  7. J. Borga, M. Bouvel, V. Féray, and B. Stufler. A decorated tree approach to random permutations in substitution-closed classes. arXiv preprint, 2019. URL: http://arxiv.org/abs/1904.07135.
  8. J. Borga and E. Slivken. Square permutations are typically rectangular. Annals of Applied Probability, to appear, 2019. Google Scholar
  9. M. Çağlar, H. Hajri, and A. H. Karakuş. Correlated coalescing Brownian flows on ℝ and the circle. ALEA Lat. Am. J. Probab. Math. Stat., 15(2):1447-1464, 2018. Google Scholar
  10. D. Denisov and V. Wachtel. Random walks in cones. Ann. Probab., 43(3):992-1044, 2015. URL: https://doi.org/10.1214/13-AOP867.
  11. T. Dokos and I. Pak. The expected shape of random doubly alternating Baxter permutations. Online J. Anal. Comb., 9:12, 2014. Google Scholar
  12. J. Duraj and V. Wachtel. Invariance principles for random walks in cones. arXiv preprint, 2015. URL: http://arxiv.org/abs/1508.07966.
  13. S. Felsner, É. Fusy, M. Noy, and D. Orden. Bijections for Baxter families and related objects. J. Combin. Theory Ser. A, 118(3):993-1020, 2011. URL: https://doi.org/10.1016/j.jcta.2010.03.017.
  14. E. Gwynne, N. Holden, and X. Sun. Joint scaling limit of a bipolar-oriented triangulation and its dual in the Peanosphere sense. arXiv preprint, 2016. URL: http://arxiv.org/abs/1603.01194.
  15. E. Gwynne, N. Holden, and X. Sun. Mating of trees for random planar maps and Liouville quantum gravity: a survey. arXiv preprint, 2019. URL: http://arxiv.org/abs/1910.04713.
  16. C. Hoffman, D. Rizzolo, and E. Slivken. Scaling limits of permutations avoiding long decreasing sequences. arXiv preprint, 2019. URL: http://arxiv.org/abs/1911.04982.
  17. C. Hoppen, Y. Kohayakawa, C. G. Moreira, B. Ráth, and R. M. Sampaio. Limits of permutation sequences. Journal of Combinatorial Theory, Series B, 103(1):93-113, 2013. Google Scholar
  18. R. Kenyon, D. Král', C. Radin, and P. Winkler. Permutations with fixed pattern densities. Random Structures & Algorithms, 2019. URL: https://doi.org/10.1002/rsa.20882.
  19. R. Kenyon, J. Miller, S. Sheffield, and D. B. Wilson. Bipolar orientations on planar maps and SLE_12. Ann. Probab., 47(3):1240-1269, 2019. URL: https://doi.org/10.1214/18-AOP1282.
  20. M. Maazoun. On the Brownian separable permuton. Combinatorics, Probability and Computing, page 1–26, 2019. URL: https://doi.org/10.1017/S0963548319000300.
  21. N. Madras and H. Liu. Random pattern-avoiding permutations. Algorithmic Probability and Combinatorics, AMS, Providence, RI, pages 173-194, 2010. Google Scholar
  22. S. Miner and I. Pak. The shape of random pattern-avoiding permutations. Adv. in Appl. Math., 55:86-130, 2014. URL: https://doi.org/10.1016/j.aam.2013.12.004.
  23. V. Prokaj. The solution of the perturbed Tanaka-equation is pathwise unique. Ann. Probab., 41(3B):2376-2400, 2013. URL: https://doi.org/10.1214/11-AOP716.
  24. D. Revuz and M. Yor. Continuous martingales and Brownian motion, volume 293. Springer Science & Business Media, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact