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
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.


References [Enhancements On Off] (What's this?)

References

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
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