On the Threshold for Triangulations Inside Convex Polygons
Open Access
- 7 September 2026
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 69 (2) , e70093
Abstract
Start with a large convex polygon and add all other edges inside independently with probability . At what critical threshold do triangulations of the polygon begin to appear? The first author and Gravner asked this question and observed that , using the relationship with the Catalan numbers and a coupling with oriented site percolation on . More recently, Archer, Hartarsky, the first author, Olesker‐Taylor, Schapira, and Valesin proved that , where is the Catalan exponential growth rate and is the critical threshold for oriented percolation. The upper bound is strict, but nonquantitative and follows by a renormalization argument. In this work, we show that using a simple ear clipping algorithm, which can be analyzed by comparing with random walks with negative drift. This bound is closer to the truth (perhaps near 0.4) and shows that most configurations of edges inside large convex polygons contain triangulations.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Catalan percolationProbability Theory and Related Fields, 2025
- The threshold for the square of a Hamilton cycleProceedings of the American Mathematical Society, 2021
- Brochette percolationIsrael Journal of Mathematics, 2018
- Graph bootstrap percolationRandom Structures & Algorithms, 2012
- Spanning Subgraphs of Random GraphsCombinatorics, Probability and Computing, 2000
- Bootstrap percolation in a polluted environmentJournal of Statistical Physics, 1997
- Strict monotonicity for critical points in percolation and ferromagnetic modelsJournal of Statistical Physics, 1991
- Spanning maximal planar subgraphs of random graphsRandom Structures & Algorithms, 1991
- On the asymptotic behaviour of first passage times for transient random walkProbability Theory and Related Fields, 1989
- On two-dimensional directed percolationJournal of Physics A: General Physics, 1988