## Minimum weight disk triangulations and fillings

HTML articles powered by AMS MathViewer

- by Itai Benjamini, Eyal Lubetzky and Yuval Peled PDF
- Trans. Amer. Math. Soc.
**374**(2021), 3265-3287 Request permission

## Abstract:

We study the minimum total weight of a disk triangulation using vertices out of $\{1,\ldots ,n\}$, where the boundary is the triangle $(123)$ and the $\binom {n}3$ triangles have independent weights, e.g. $\mathrm {Exp}(1)$ or $\mathrm {U}(0,1)$. We show that for explicit constants $c_1,c_2>0$, this minimum is $c_1 \frac {\log n}{\sqrt n} + c_2 \frac {\log \log n}{\sqrt n} + \frac {Y_n}{\sqrt n}$, where the random variable $Y_n$ is tight, and it is attained by a triangulation that consists of $\frac 14\log n + O_{P}(\sqrt {\log n})$ vertices. Moreover, for disk triangulations that are canonical, in that no inner triangle contains all but $O(1)$ of the vertices, the minimum weight has the above form with the law of $Y_n$ converging weakly to a shifted Gumbel. In addition, we prove that, with high probability, the minimum weights of a homological filling and a homotopical filling of the cycle $(123)$ are both attained by the minimum weight disk triangulation.## References

- Aaron Abrams, Noel Brady, Pallavi Dani, and Robert Young,
*Homological and homotopical Dehn functions are different*, Proc. Natl. Acad. Sci. USA**110**(2013), no. 48, 19206–19212. MR**3153947**, DOI 10.1073/pnas.1207377110 - David Aldous and J. Michael Steele,
*The objective method: probabilistic combinatorial optimization and local weak convergence*, Probability on discrete structures, Encyclopaedia Math. Sci., vol. 110, Springer, Berlin, 2004, pp. 1–72. MR**2023650**, DOI 10.1007/978-3-662-09444-0_{1} - David J. Aldous,
*The $\zeta (2)$ limit in the random assignment problem*, Random Structures Algorithms**18**(2001), no. 4, 381–418. MR**1839499**, DOI 10.1002/rsa.1015 - Lior Aronshtam, Nathan Linial, Tomasz Łuczak, and Roy Meshulam,
*Collapsibility and vanishing of top homology in random simplicial complexes*, Discrete Comput. Geom.**49**(2013), no. 2, 317–334. MR**3017914**, DOI 10.1007/s00454-012-9483-8 - Eric Babson, Christopher Hoffman, and Matthew Kahle,
*The fundamental group of random 2-complexes*, J. Amer. Math. Soc.**24**(2011), no. 1, 1–28. MR**2726597**, DOI 10.1090/S0894-0347-2010-00677-7 - A. D. Barbour, Lars Holst, and Svante Janson,
*Poisson approximation*, Oxford Studies in Probability, vol. 2, The Clarendon Press, Oxford University Press, New York, 1992. Oxford Science Publications. MR**1163825** - Shankar Bhamidi and Remco van der Hofstad,
*Diameter of the stochastic mean-field model of distance*, Combin. Probab. Comput.**26**(2017), no. 6, 797–825. MR**3714992**, DOI 10.1017/S0963548317000232 - Shankar Bhamidi, Remco van der Hofstad, and Gerard Hooghiemstra,
*Universality for first passage percolation on sparse random graphs*, Ann. Probab.**45**(2017), no. 4, 2568–2630. MR**3693970**, DOI 10.1214/16-AOP1120 - William G. Brown,
*Enumeration of triangulations of the disk*, Proc. London Math. Soc. (3)**14**(1964), 746–768. MR**168485**, DOI 10.1112/plms/s3-14.4.746 - T. Budzinski and B. Louf,
*Local limits of uniform triangulations in high genus*, arXiv preprint arXiv:1902.00492, 2019. - Dominic Dotterrer, Larry Guth, and Matthew Kahle,
*2-complexes with large 2-girth*, Discrete Comput. Geom.**59**(2018), no. 2, 383–412. MR**3755728**, DOI 10.1007/s00454-017-9926-3 - Samuel Eilenberg,
*On the problems of topology*, Ann. of Math. (2)**50**(1949), 247–260. MR**30189**, DOI 10.2307/1969448 - A. M. Frieze,
*On the value of a random minimum spanning tree problem*, Discrete Appl. Math.**10**(1985), no. 1, 47–56. MR**770868**, DOI 10.1016/0166-218X(85)90058-7 - Zhicheng Gao,
*A pattern for the asymptotic number of rooted maps on surfaces*, J. Combin. Theory Ser. A**64**(1993), no. 2, 246–264. MR**1245161**, DOI 10.1016/0097-3165(93)90097-R - Allen Hatcher,
*Algebraic topology*, Cambridge University Press, Cambridge, 2002. MR**1867354** - Yasuaki Hiraoka and Tomoyuki Shirai,
*Minimum spanning acycle and lifetime of persistent homology in the Linial-Meshulam process*, Random Structures Algorithms**51**(2017), no. 2, 315–340. MR**3683365**, DOI 10.1002/rsa.20718 - Svante Janson,
*Coupling and Poisson approximation*, Acta Appl. Math.**34**(1994), no. 1-2, 7–15. MR**1273843**, DOI 10.1007/BF00994254 - Svante Janson,
*One, two and three times $\log n/n$ for paths in a complete graph with random weights*, Combin. Probab. Comput.**8**(1999), no. 4, 347–361. Random graphs and combinatorial structures (Oberwolfach, 1997). MR**1723648**, DOI 10.1017/S0963548399003892 - Jacob E. Goodman, Joseph O’Rourke, and Csaba D. Tóth (eds.),
*Handbook of discrete and computational geometry*, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2018. Third edition of [ MR1730156]. MR**3793131** - Matthew Kahle and Boris Pittel,
*Inside the critical window for cohomology of random $k$-complexes*, Random Structures Algorithms**48**(2016), no. 1, 102–124. MR**3432573**, DOI 10.1002/rsa.20577 - Nathan Linial and Roy Meshulam,
*Homological connectivity of random 2-complexes*, Combinatorica**26**(2006), no. 4, 475–487. MR**2260850**, DOI 10.1007/s00493-006-0027-9 - Z. Luria and Y. Peled,
*On simple connectivity of random 2-complexes*, Preprint, available at arXiv:1806.03351 (2018). - Roger C. Lyndon and Paul E. Schupp,
*Combinatorial group theory*, Classics in Mathematics, Springer-Verlag, Berlin, 2001. Reprint of the 1977 edition. MR**1812024**, DOI 10.1007/978-3-642-61896-3 - W. T. Tutte,
*A census of planar triangulations*, Canadian J. Math.**14**(1962), 21–38. MR**130841**, DOI 10.4153/CJM-1962-002-9

## Additional Information

**Itai Benjamini**- Affiliation: Department of Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel
- MR Author ID: 311800
- Email: itai.benjamini@weizmann.ac.il
**Eyal Lubetzky**- Affiliation: Courant Institute, New York University, 251 Mercer Street, New York, New York 10012
- MR Author ID: 787713
- ORCID: 0000-0002-2281-3542
- Email: eyal@courant.nyu.edu
**Yuval Peled**- Affiliation: Courant Institute, New York University, 251 Mercer Street, New York, New York 10012
- MR Author ID: 1064288
- Email: yuval.peled@courant.nyu.edu
- Received by editor(s): January 27, 2020
- Received by editor(s) in revised form: July 23, 2020
- Published electronically: February 12, 2021
- Additional Notes: The second author was supported in part by NSF grant DMS-1812095.
- © Copyright 2021 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**374**(2021), 3265-3287 - MSC (2020): Primary 57K20, 60C05
- DOI: https://doi.org/10.1090/tran/8255
- MathSciNet review: 4237948