Schnyder woods, SLE₁₆, and Liouville quantum gravity

Li, Yiting; Sun, Xin; Watson, Samuel

doi:10.1090/tran/8887

Schnyder woods, SLE$_{16}$, and Liouville quantum gravity
HTML articles powered by AMS MathViewer

by Yiting Li, Xin Sun and Samuel S. Watson;

Trans. Amer. Math. Soc. 377 (2024), 2439-2493

DOI: https://doi.org/10.1090/tran/8887

Published electronically: February 14, 2024

HTML | PDF | Request permission

Abstract:

In 1990, Schnyder used a 3-spanning-tree decomposition of a simple triangulation, now known as the Schnyder wood, to give a fundamental grid-embedding algorithm for planar maps. In the framework of mating of trees, a uniformly sampled Schnyder-wood-decorated triangulation can produce a triple of random walks. We show that these three walks converge in the scaling limit to three Brownian motions produced in the mating-of-trees framework by Liouville quantum gravity (LQG) with parameter $1$, decorated with a triple of SLE$_{16}$’s curves. These three SLE$_{16}$’s curves are coupled such that the angle difference between them is $2\pi /3$ in imaginary geometry. Our convergence result provides a description of the continuum limit of Schnyder’s embedding algorithm via LQG and SLE.

References

Juhan Aru, Yichao Huang, and Xin Sun, Two perspectives of the 2D unit area quantum sphere and their equivalence, Comm. Math. Phys. 356 (2017), no. 1, 261–283. MR 3694028, DOI 10.1007/s00220-017-2979-6
Rodney Baxter, F model on a triangular lattice, J. Math. Phys. 10 (1969), no. 7, 1211–1216, DOI 10.1063/1.1664960.
Itai Benjamini and Oded Schramm, Recurrence of distributional limits of finite planar graphs, Electron. J. Probab. 6 (2001), no. 23, 13. MR 1873300, DOI 10.1214/EJP.v6-96
NathanaÎl Berestycki and Ellen Powell, Gaussian free field, Liouville quantum gravity and Gaussian multiplicative chaos, Lecture Notes, 2021, https://homepage.univie.ac.at/nathanael.berestycki/Articles/master.pdf.
Olivier Bernardi, Bijective counting of tree-rooted maps and shuffles of parenthesis systems, Electron. J. Combin. 14 (2007), no. 1, Research Paper 9, 36. MR 2285813, DOI 10.37236/928
Olivier Bernardi and Nicolas Bonichon, Intervals in Catalan lattices and realizers of triangulations, J. Combin. Theory Ser. A 116 (2009), no. 1, 55–75. MR 2469248, DOI 10.1016/j.jcta.2008.05.005
Olivier Bernardi and Éric Fusy, Schnyder decompositions for regular plane graphs and application to drawing, Algorithmica 62 (2012), no. 3-4, 1159–1197. MR 2871142, DOI 10.1007/s00453-011-9514-5
Olivier Bernardi, Nina Holden, and Xin Sun, Percolation on triangulations: a bijective path to Liouville quantum gravity, Mem. Amer. Math. Soc., To appear.
Dmitry Chelkak, Hugo Duminil-Copin, Clément Hongler, Antti Kemppainen, and Stanislav Smirnov, Convergence of Ising interfaces to Schramm’s SLE curves, C. R. Math. Acad. Sci. Paris 352 (2014), no. 2, 157–161 (English, with English and French summaries). MR 3151886, DOI 10.1016/j.crma.2013.12.002
François David, Antti Kupiainen, Rémi Rhodes, and Vincent Vargas, Liouville quantum gravity on the Riemann sphere, Comm. Math. Phys. 342 (2016), no. 3, 869–907. MR 3465434, DOI 10.1007/s00220-016-2572-4
Giuseppe Di Battista and Fabrizio Frati, Drawing trees, outerplanar graphs, series-parallel graphs, and planar graphs in a small area, Thirty essays on geometric graph theory, Springer, New York, 2013, pp. 121–165. MR 3205153, DOI 10.1007/978-1-4614-0110-0_{9}
Jian Ding, Julien Dubédat, Alexander Dunlap, and Hugo Falconet, Tightness of Liouville first passage percolation for $\gamma \in (0,2)$, Publ. Math. Inst. Hautes Études Sci. 132 (2020), 353–403. MR 4179836, DOI 10.1007/s10240-020-00121-1
M. D. Donsker and S. R. S. Varadhan, Asymptotic evaluation of certain Markov process expectations for large time. I. II, Comm. Pure Appl. Math. 28 (1975), 1–47; ibid. 28 (1975), 279–301. MR 386024, DOI 10.1002/cpa.3160280102
M. D. Donsker and S. R. S. Varadhan, Asymptotic evaluation of certain Markov process expectations for large time. I. II, Comm. Pure Appl. Math. 28 (1975), 1–47; ibid. 28 (1975), 279–301. MR 386024, DOI 10.1002/cpa.3160280102
Bertrand Duplantier, Jason Miller, and Scott Sheffield, Liouville quantum gravity as a mating of trees, Astérisque 427 (2021), viii+257 (English, with English and French summaries). MR 4340069, DOI 10.24033/ast
Bertrand Duplantier and Scott Sheffield, Liouville quantum gravity and KPZ, Invent. Math. 185 (2011), no. 2, 333–393. MR 2819163, DOI 10.1007/s00222-010-0308-1
Jetlir Duraj and Vitali Wachtel, Invariance principles for random walks in cones, Stochastic Process. Appl. 130 (2020), no. 7, 3920–3942. MR 4102254, DOI 10.1016/j.spa.2019.11.004
István Fáry, On straight line representation of planar graphs, Acta Univ. Szeged. Sect. Sci. Math. 11 (1948), 229–233. MR 26311
Stefan Felsner, Éric Fusy, Marc Noy, and David Orden, Bijections for Baxter families and related objects, J. Combin. Theory Ser. A 118 (2011), no. 3, 993–1020. MR 2763051, DOI 10.1016/j.jcta.2010.03.017
Stefan Felsner and Florian Zickfeld, Schnyder woods and orthogonal surfaces, Discrete Comput. Geom. 40 (2008), no. 1, 103–126. MR 2429650, DOI 10.1007/s00454-007-9027-9
H. de Fraysseix, J. Pach, and R. Pollack, How to draw a planar graph on a grid, Combinatorica 10 (1990), no. 1, 41–51. MR 1075065, DOI 10.1007/BF02122694
Ewain Gwynne, Nina Holden, Jason Miller, and Xin Sun, Brownian motion correlation in the peanosphere for $\kappa >8$, Ann. Inst. Henri Poincaré Probab. Stat. 53 (2017), no. 4, 1866–1889 (English, with English and French summaries). MR 3729638, DOI 10.1214/16-AIHP774
Ewain Gwynne, Nina Holden, and Xin Sun, Joint scaling limit of a bipolar-oriented triangulation and its dual in the peanosphere sense, arXiv:1603.01194.
Ewain Gwynne, Random surfaces and Liouville quantum gravity, Notices Amer. Math. Soc. 67 (2020), no. 4, 484–491. MR 4186266, DOI 10.1090/noti
Ewain Gwynne, Nina Holden, and Xin Sun, A mating-of-trees approach for graph distances in random planar maps, Probab. Theory Related Fields 177 (2020), no. 3-4, 1043–1102. MR 4126936, DOI 10.1007/s00440-020-00969-8
Ewain Gwynne, Adrien Kassel, Jason Miller, and David B. Wilson, Active spanning trees with bending energy on planar maps and SLE-decorated Liouville quantum gravity for $\kappa > 8$, Comm. Math. Phys. 358 (2018), no. 3, 1065–1115. MR 3778352, DOI 10.1007/s00220-018-3104-1
Ewain Gwynne, Cheng Mao, and Xin Sun, Scaling limits for the critical Fortuin-Kasteleyn model on a random planar map I: Cone times, Ann. Inst. Henri Poincaré Probab. Stat. 55 (2019), no. 1, 1–60. MR 3901640, DOI 10.1214/17-aihp874
Ewain Gwynne and Jason Miller, Existence and uniqueness of the Liouville quantum gravity metric for $\gamma \in (0,2)$, Invent. Math. 223 (2021), no. 1, 213–333. MR 4199443, DOI 10.1007/s00222-020-00991-6
Ewain Gwynne, Jason Miller, and Scott Sheffield, The Tutte embedding of the Poisson-Voronoi tessellation of the Brownian disk converges to $\sqrt {8/3}$-Liouville quantum gravity, Comm. Math. Phys. 374 (2020), no. 2, 735–784. MR 4072229, DOI 10.1007/s00220-019-03610-5
Ewain Gwynne, Jason Miller, and Scott Sheffield, The Tutte embedding of the mated-CRT map converges to Liouville quantum gravity, Ann. Probab. 49 (2021), no. 4, 1677–1717. MR 4260465, DOI 10.1214/20-aop1487
Ewain Gwynne, Jason Miller, and Scott Sheffield, An invariance principle for ergodic scale-free random environments, Acta Math. 228 (2022), no. 2, 303–384. MR 4448682, DOI 10.4310/ACTA.2022.v228.n2.a2
Ewain Gwynne and Xin Sun, Scaling limits for the critical Fortuin-Kasteleyn model on a random planar map II: local estimates and empty reduced word exponent, Electron. J. Probab. 22 (2017), Paper No. 45, 56. MR 3661659, DOI 10.1214/17-EJP64
Ewain Gwynne and Xin Sun, Scaling limits for the critical Fortuin-Kasteleyn model on a random planar map III: finite volume case, arXiv:1510.06346.
Nina Holden and Xin Sun, Convergence of uniform triangulations under the Cardy embedding, Acta Math., To appear.
Nina Holden and Xin Sun, SLE as a mating of trees in Euclidean geometry, Comm. Math. Phys. 364 (2018), no. 1, 171–201. MR 3861296, DOI 10.1007/s00220-018-3149-1
Svante Janson, Tail bounds for sums of geometric and exponential variables, Statist. Probab. Lett. 135 (2018), 1–6. MR 3758253, DOI 10.1016/j.spl.2017.11.017
Richard Kenyon, Jason Miller, Scott Sheffield, and David B. Wilson, Bipolar orientations on planar maps and $\textrm {SLE}_{12}$, Ann. Probab. 47 (2019), no. 3, 1240–1269. MR 3945746, DOI 10.1214/18-AOP1282
Richard Kenyon, Jason Miller, Scott Sheffield, and David B. Wilson, The six-vertex model and Schramm-Loewner evolution, Phys. Rev. E 95 (2017), no. 5, 052146, DOI 10.1103/PhysRevE.95.052146.
Sergei K. Lando and Alexander K. Zvonkin, Graphs on surfaces and their applications, Encyclopaedia of Mathematical Sciences, vol. 141, Springer-Verlag, Berlin, 2004. With an appendix by Don B. Zagier; Low-Dimensional Topology, II. MR 2036721, DOI 10.1007/978-3-540-38361-1
Gregory F. Lawler and Vlada Limic, Random walk: a modern introduction, Cambridge Studies in Advanced Mathematics, vol. 123, Cambridge University Press, Cambridge, 2010. MR 2677157, DOI 10.1017/CBO9780511750854
Gregory F. Lawler, Oded Schramm, and Wendelin Werner, On the scaling limit of planar self-avoiding walk, Fractal geometry and applications: a jubilee of Benoît Mandelbrot, Part 2, Proc. Sympos. Pure Math., vol. 72, Amer. Math. Soc., Providence, RI, 2004, pp. 339–364. MR 2112127, DOI 10.1090/pspum/072.2/2112127
Gregory F. Lawler, Oded Schramm, and Wendelin Werner, Conformal invariance of planar loop-erased random walks and uniform spanning trees, Ann. Probab. 32 (2004), no. 1B, 939–995. MR 2044671, DOI 10.1214/aop/1079021469
Jean-François Le Gall, Random trees and applications, Probab. Surv. 2 (2005), 245–311. MR 2203728, DOI 10.1214/154957805100000140
Jean-François Le Gall, Uniqueness and universality of the Brownian map, Ann. Probab. 41 (2013), no. 4, 2880–2960. MR 3112934, DOI 10.1214/12-AOP792
Martin Loebl and Jean-Sébastien Sereni, Graph counting, Lecture 7, 2009, https://lbgi.fr/~sereni/GC_Spring09.html.
Grégory Miermont, The Brownian map is the scaling limit of uniform random plane quadrangulations, Acta Math. 210 (2013), no. 2, 319–401. MR 3070569, DOI 10.1007/s11511-013-0096-8
Jason Miller and Scott Sheffield, Imaginary geometry I: interacting SLEs, Probab. Theory Related Fields 164 (2016), no. 3-4, 553–705. MR 3477777, DOI 10.1007/s00440-016-0698-0
Jason Miller and Scott Sheffield, Imaginary geometry IV: interior rays, whole-plane reversibility, and space-filling trees, Probab. Theory Related Fields 169 (2017), no. 3-4, 729–869. MR 3719057, DOI 10.1007/s00440-017-0780-2
Jason Miller and Scott Sheffield, Liouville quantum gravity and the Brownian map I: the $\textrm {QLE}(8/3,0)$ metric, Invent. Math. 219 (2020), no. 1, 75–152. MR 4050102, DOI 10.1007/s00222-019-00905-1
Jason Miller and Scott Sheffield, Liouville quantum gravity spheres as matings of finite-diameter trees, Ann. Inst. Henri Poincaré Probab. Stat. 55 (2019), no. 3, 1712–1750 (English, with English and French summaries). MR 4010949, DOI 10.1214/18-aihp932
Jason Miller and Scott Sheffield, Liouville quantum gravity and the Brownian map II: Geodesics and continuity of the embedding, Ann. Probab. 49 (2021), no. 6, 2732–2829. MR 4348679, DOI 10.1214/21-aop1506
Jason Miller and Scott Sheffield, Liouville quantum gravity and the Brownian map III: the conformal structure is determined, Probab. Theory Related Fields 179 (2021), no. 3-4, 1183–1211. MR 4242633, DOI 10.1007/s00440-021-01026-8
Sarah Miracle, Dana Randall, Amanda Pascoe Streib, and Prasad Tetali, Sampling and counting 3-orientations of planar triangulations, SIAM J. Discrete Math. 30 (2016), no. 2, 801–831. MR 3490888, DOI 10.1137/140965752
R. C. Mullin, On the enumeration of tree-rooted maps, Canadian J. Math. 19 (1967), 174–183. MR 205882, DOI 10.4153/CJM-1967-010-x
A. M. Polyakov, Quantum geometry of bosonic strings, Phys. Lett. B 103 (1981), no. 3, 207–210. MR 623209, DOI 10.1016/0370-2693(81)90743-7
Daniel Revuz and Marc Yor, Continuous martingales and Brownian motion, 3rd ed., Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 293, Springer-Verlag, Berlin, 1999. MR 1725357, DOI 10.1007/978-3-662-06400-9
Walter Schnyder, Planar graphs and poset dimension, Order 5 (1989), no. 4, 323–343. MR 1010382, DOI 10.1007/BF00353652
Walter Schnyder, Embedding planar graphs on the grid, SODA ’90: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1990, pp. 138–148.
Oded Schramm, Scaling limits of loop-erased random walks and uniform spanning trees, Israel J. Math. 118 (2000), 221–288. MR 1776084, DOI 10.1007/BF02803524
Oded Schramm and Scott Sheffield, Contour lines of the two-dimensional discrete Gaussian free field, Acta Math. 202 (2009), no. 1, 21–137. MR 2486487, DOI 10.1007/s11511-009-0034-y
Scott Sheffield, Conformal weldings of random surfaces: SLE and the quantum gravity zipper, Ann. Probab. 44 (2016), no. 5, 3474–3545. MR 3551203, DOI 10.1214/15-AOP1055
Scott Sheffield, Quantum gravity and inventory accumulation, Ann. Probab. 44 (2016), no. 6, 3804–3848. MR 3572324, DOI 10.1214/15-AOP1061
Stanislav Smirnov, Critical percolation in the plane: conformal invariance, Cardy’s formula, scaling limits, C. R. Acad. Sci. Paris Sér. I Math. 333 (2001), no. 3, 239–244 (English, with English and French summaries). MR 1851632, DOI 10.1016/S0764-4442(01)01991-7
Stanislav Smirnov, Conformal invariance in random cluster models. I. Holomorphic fermions in the Ising model, Ann. of Math. (2) 172 (2010), no. 2, 1435–1467. MR 2680496, DOI 10.4007/annals.2010.172.1441
Xin Sun and Samuel S. Watson, The scaling limit of the Schnyder embedding and Liouville quantum gravity with $\gamma =1$, 2017, In preparation.
Roberto Tamassia (ed.), Handbook of graph drawing and visualization, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2014. MR 3156770