Combinatorics Seminar

When: Sunday, December 22, 10am
Where: Schreiber 309
Speaker: Yuval Peled, New York University
Title: Minimum weight disk triangulations and fillings

Abstract:

We study the minimum weight of a triangulation of a disk with fixed boundary vertices $1,2,3$ using any number of inner vertices whose labels are taken from $[n]=\{1,\ldots,n\}$, in the setting where every triangle in ${[n] \choose 3}$ is assigned, for instance, an independent rate-1 exponential weight.

Our first result establishes 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 $\frac14\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, we further identify the limiting law of the centered minimum to be 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.

Joint work with Itai Benjamini and Eyal Lubetzky.