Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

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 $ \{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_{\textsc {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 [Enhancements On Off] (What's this?)


Similar Articles

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