On the threshold for triangulations inside convex polygons
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918139880538112 |
|---|---|
| author | Kolesnik, Brett Zakharov, Georgii Zhukovskii, Maksim |
| author_facet | Kolesnik, Brett Zakharov, Georgii Zhukovskii, Maksim |
| contents | Start with a large convex polygon and add all other edges inside independently with probability $p$. At what critical threshold $p_c$ do triangulations of the polygon begin to appear?
The first author and Gravner asked this question, and observed that $p_c=Θ(1)$, using the relationship with the Catalan numbers and a coupling with oriented site percolation on ${\mathbb Z}^2$. More recently, Archer, Hartarsky, the first author, Olesker-Taylor, Schapira and Valesin proved that $1/4<p_c<p_c^o$, where $1/4$ is the Catalan exponential growth rate and $p_c^o$ is the critical threshold for oriented percolation. The upper bound is strict, but non-quantitative, and follows by a renormalization argument.
We show that $p_c<1/2$ using a simple ear clipping algorithm, which can be analyzed using the gambler's ruin problem. This bound is closer to the truth (perhaps near $0.4$) and shows that most configurations of edges inside large convex polygons contain triangulations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10160 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the threshold for triangulations inside convex polygons Kolesnik, Brett Zakharov, Georgii Zhukovskii, Maksim Probability Combinatorics 60K35, 82B43 Start with a large convex polygon and add all other edges inside independently with probability $p$. At what critical threshold $p_c$ do triangulations of the polygon begin to appear? The first author and Gravner asked this question, and observed that $p_c=Θ(1)$, using the relationship with the Catalan numbers and a coupling with oriented site percolation on ${\mathbb Z}^2$. More recently, Archer, Hartarsky, the first author, Olesker-Taylor, Schapira and Valesin proved that $1/4<p_c<p_c^o$, where $1/4$ is the Catalan exponential growth rate and $p_c^o$ is the critical threshold for oriented percolation. The upper bound is strict, but non-quantitative, and follows by a renormalization argument. We show that $p_c<1/2$ using a simple ear clipping algorithm, which can be analyzed using the gambler's ruin problem. This bound is closer to the truth (perhaps near $0.4$) and shows that most configurations of edges inside large convex polygons contain triangulations. |
| title | On the threshold for triangulations inside convex polygons |
| topic | Probability Combinatorics 60K35, 82B43 |
| url | https://arxiv.org/abs/2509.10160 |