×

Mating of discrete trees and walks in the quarter-plane. (English) Zbl 1473.05049

Summary: We give a general construction of triangulations starting from a walk in the quarter plane with small steps, which is a discrete version of the mating of trees. We use a special instance of this construction to give a bijection between maps equipped with a rooted spanning tree and walks in the quarter plane. We also show how the construction allows to recover several known bijections between such objects in a uniform way.

MSC:

05C05 Trees
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
05A15 Exact enumeration problems, generating functions
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Albenque, D. Poulalhon. A generic method for bijections between blossoming trees and planar maps.Electron. J. Combin.22 (2015), #P2.38. · Zbl 1327.05028
[2] X. Buff, A.L. Epstein, S. Koch, D. Meyer, K. Pilgrim, M. Rees, T. Lei. Questions about polynomial matings.Ann. Fac. Sci. Toulouse Math.(6) 21 (2012), no. 5, 1149-1176. · Zbl 1364.37099
[3] N. Borie. Three-dimensional Catalan numbers and product-coproduct prographs. FPSAC 29,S´eminaire Lotharingien de combinatoire76B (2017) Article]39. · Zbl 1384.05165
[4] O. Bernardi, N. Bonichon. Intervals in Catalan lattices and realizers of triangulations. J. Combin. Theory Ser. A116 (2009), no. 1, 55-75. · Zbl 1161.06001
[5] O. Bernardi. Bijective counting of Kreweras walks and loopless triangulations.J. Combin. Theory Ser. A114 (2007), no. 5, 931-956. · Zbl 1119.05006
[6] O. Bernardi, N. Holden, X. Sun. Percolation on triangulations: a bijective path to quantum gravity.arXiv:1807.01684
[7] M. Bousquet-M´elou, M. Mishna. Walks with small steps in the quarter plane.Algorithmic probability and combinatorics, 1-39,Contemp. Math., 520, Amer. Math. Soc., Providence, RI, 2010. · Zbl 1209.05008
[8] B. Duplantier, J. Miller, S. Sheffield. Liouville quantum gravity as a mating of trees, arXiv:1409.7055 · Zbl 1503.60003
[9] E. Gwynne, N. Holden, X. Sun. Mating of trees for random planar maps and Liouville quantum gravity: a survey,arXiv:1910.04713 · Zbl 1464.60011
[10] R. Kenyon, J. Miller, S. Sheffield, D. Wilson. Bipolar orientations on planar maps andSLE12.Ann. Probab.47 (2019), no. 3, 1240-1269. · Zbl 1466.60170
[11] J. F. Le Gall, F. Paulin. Scaling limits of bipartite planar maps are homeomorphic to the 2-sphere.Geom. Funct. Anal.18 (2008), no. 3, 893-918. · Zbl 1166.60006
[12] Y. Li, X. Sun, S.S. Watson. Schnyder woods,SLE16, and Liouville quantum gravity. arXiv:1705.03573
[13] G. Schaeffer. Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees.Electron. J. Combin.4 (1997), #R20. · Zbl 0885.05076
[14] G. Schaeffer. Planar maps.Handbook of enumerative combinatorics.335-395,Discrete Math. Appl.(Boca Raton), CRC Press, Boca Raton, FL, 2015. · Zbl 1326.05036
[15] R.P. Stanley.Enumerative combinatorics, vol. 2.Cambridge University Press 1999. the electronic journal of combinatorics28(3)(2021), #P3 · Zbl 0928.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.