Minimum weight disk triangulations and fillings

17 November 2020
Yuval Peled

Further Information: 

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.


We study the minimum total weight of a disk triangulation using any number of vertices out of $\{1,..,n\}$ where the boundary is fixed and the $n \choose 3$ triangles have independent rate-1 exponential weights. We show that, with high probability, the minimum weight is equal to $(c+o(1))n-1/2\log n$ for an explicit constant $c$. Further, 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. We will discuss a related open problem concerning simple-connectivity of random simplicial complexes, where a similar phenomenon is conjectured to hold. Based on joint works with Itai Benjamini, Eyal Lubetzky, and Zur Luria.

  • Combinatorial Theory Seminar