Minimum weight disk triangulations and fillings
Authors:
Itai Benjamini, Eyal Lubetzky and Yuval Peled
Journal:
Trans. Amer. Math. Soc. 374 (2021), 3265-3287
MSC (2020):
Primary 57K20, 60C05
DOI:
https://doi.org/10.1090/tran/8255
Published electronically:
February 12, 2021
MathSciNet review:
4237948
Full-text PDF
Abstract | References | Similar Articles | Additional Information
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.
- 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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1007/s00454-017-9926-3
- Samuel Eilenberg, On the problems of topology, Ann. of Math. (2) 50 (1949), 247β260. MR 30189, DOI https://doi.org/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 https://doi.org/10.1016/0166-218X%2885%2990058-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 https://doi.org/10.1016/0097-3165%2893%2990097-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 https://doi.org/10.1002/rsa.20718
- Svante Janson, Coupling and Poisson approximation, Acta Appl. Math. 34 (1994), no. 1-2, 7β15. MR 1273843, DOI https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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
- W. T. Tutte, A census of planar triangulations, Canadian J. Math. 14 (1962), 21β38. MR 130841, DOI https://doi.org/10.4153/CJM-1962-002-9
Retrieve articles in Transactions of the American Mathematical Society with MSC (2020): 57K20, 60C05
Retrieve articles in all journals with MSC (2020): 57K20, 60C05
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.
Article copyright:
© Copyright 2021
American Mathematical Society