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
Full-text PDF
Abstract | References | Similar Articles | Additional Information
Abstract: We study the minimum total weight of a disk triangulation using vertices out of , where the boundary is the triangle
and the
triangles have independent weights, e.g.
or
. We show that for explicit constants
, this minimum is
, where the random variable
is tight, and it is attained by a triangulation that consists of
vertices. Moreover, for disk triangulations that are canonical, in that no inner triangle contains all but
of the vertices, the minimum weight has the above form with the law of
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
are both attained by the minimum weight disk triangulation.
- [1] 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. {3153947}, https://doi.org/10.1073/pnas.1207377110
- [2] 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. {2023650}, https://doi.org/10.1007/978-3-662-09444-0_1
- [3] David J. Aldous, The 𝜁(2) limit in the random assignment problem, Random Structures Algorithms 18 (2001), no. 4, 381–418. {1839499}, https://doi.org/10.1002/rsa.1015
- [4] 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. {3017914}, https://doi.org/10.1007/s00454-012-9483-8
- [5] Eric Babson, Christopher Hoffman, and Matthew Kahle, The fundamental group of random 2-complexes, J. Amer. Math. Soc. 24 (2011), no. 1, 1–28. {2726597}, https://doi.org/10.1090/S0894-0347-2010-00677-7
- [6] 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. {1163825}
- [7] 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. {3714992}, https://doi.org/10.1017/S0963548317000232
- [8] 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. {3693970}, https://doi.org/10.1214/16-AOP1120
- [9] William G. Brown, Enumeration of triangulations of the disk, Proc. London Math. Soc. (3) 14 (1964), 746–768. {168485}, https://doi.org/10.1112/plms/s3-14.4.746
- [10]
T. Budzinski and B. Louf,
Local limits of uniform triangulations in high genus,
arXiv preprint 1902.00492, 2019. - [11] Dominic Dotterrer, Larry Guth, and Matthew Kahle, 2-complexes with large 2-girth, Discrete Comput. Geom. 59 (2018), no. 2, 383–412. {3755728}, https://doi.org/10.1007/s00454-017-9926-3
- [12] Samuel Eilenberg, On the problems of topology, Ann. of Math. (2) 50 (1949), 247–260. {30189}, https://doi.org/10.2307/1969448
- [13] A. M. Frieze, On the value of a random minimum spanning tree problem, Discrete Appl. Math. 10 (1985), no. 1, 47–56. {770868}, https://doi.org/10.1016/0166-218X(85)90058-7
- [14] Zhicheng Gao, A pattern for the asymptotic number of rooted maps on surfaces, J. Combin. Theory Ser. A 64 (1993), no. 2, 246–264. {1245161}, https://doi.org/10.1016/0097-3165(93)90097-R
- [15] Allen Hatcher, Algebraic topology, Cambridge University Press, Cambridge, 2002. {1867354}
- [16] 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. {3683365}, https://doi.org/10.1002/rsa.20718
- [17] Svante Janson, Coupling and Poisson approximation, Acta Appl. Math. 34 (1994), no. 1-2, 7–15. {1273843}, https://doi.org/10.1007/BF00994254
- [18] Svante Janson, One, two and three times log𝑛/𝑛 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). {1723648}, https://doi.org/10.1017/S0963548399003892
- [19] 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]. {3793131}
- [20] Matthew Kahle and Boris Pittel, Inside the critical window for cohomology of random 𝑘-complexes, Random Structures Algorithms 48 (2016), no. 1, 102–124. {3432573}, https://doi.org/10.1002/rsa.20577
- [21] Nathan Linial and Roy Meshulam, Homological connectivity of random 2-complexes, Combinatorica 26 (2006), no. 4, 475–487. {2260850}, https://doi.org/10.1007/s00493-006-0027-9
- [22]
Z. Luria and Y. Peled,
On simple connectivity of random 2-complexes,
Preprint, available at 1806.03351 (2018). - [23] Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Classics in Mathematics, Springer-Verlag, Berlin, 2001. Reprint of the 1977 edition. {1812024}
- [24] W. T. Tutte, A census of planar triangulations, Canadian J. Math. 14 (1962), 21–38. {130841}, 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
Email:
itai.benjamini@weizmann.ac.il
Eyal Lubetzky
Affiliation:
Courant Institute, New York University, 251 Mercer Street, New York, New York 10012
Email:
eyal@courant.nyu.edu
Yuval Peled
Affiliation:
Courant Institute, New York University, 251 Mercer Street, New York, New York 10012
Email:
yuval.peled@courant.nyu.edu
DOI:
https://doi.org/10.1090/tran/8255
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