Minimum weight disk triangulations and fillings

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.