On the threshold for triangulations inside convex polygons

Brett Kolesnik; Georgii Zakharov; Maksim Zhukovskii

REVIEW 3 major objections 4 minor 14 references

On the threshold for triangulations inside convex polygons

T0 review · 3 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The critical probability for a random set of diagonals inside a convex n-gon to contain a triangulation is strictly below 1/2; the paper proves p_c ≤ p* ≈ 0.4916.

desk verdict The result is likely true and genuinely new, but Section 5's BECA argument is too sketched—the Markov property and transition probabilities need to be formalized before the p* < 1/2 claim is rigorous. read the letter →

arxiv 2509.10160 v1 pith:DGL7XKCU submitted 2025-09-12 math.PR math.CO

Brett Kolesnik , Georgii Zakharov , Maksim Zhukovskii This is my paper

classification math.PRmath.CO MSC 60K3582B43

keywords Catalanpercolationtriangulationsconvexpolygonsrandomgraphsgambler'sruincriticalthresholdearclipping

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Open every diagonal of a large convex n-gon independently with probability p, and ask whether the resulting edge set contains a full triangulation. This paper proves that the critical threshold is strictly below 1/2: there is an explicit p* ≈ 0.4916 such that for every p > p* a triangulation appears with high probability as n grows. The argument is built from ear-clipping algorithms, which peel off boundary triangles one at a time and turn the problem into a gambler's ruin walk with negative drift. This improves on earlier bounds that tied the threshold to oriented percolation, and it makes precise the sense in which most random configurations of internal edges contain a triangulation.

What carries the argument

Key machinery: greedy and 'better' ear-clipping algorithms (GECA and BECA). GECA repeatedly removes an ear when the edge closing it is present, otherwise advances the boundary point; its list of active vertices performs a nearest-neighbour random walk, so the gambler's ruin formula bounds the chance of failure. BECA adds a local optimisation step that queries a small set of adjacencies and then changes list length by −2, −1, 0, +1, or +2, giving a negative-drift Markov chain whenever p > p* ≈ 0.4916. The gambler's ruin bounds for walks with bounded jumps convert this drift into a high-probability guarantee of triangulation.

What would settle it

Compute the drift polynomial Δ(p) = 2p^6 − 6p^5 + 4p^4 + 5p^3 − 9p^2 + p + 1. The theorem requires Δ(p*) < 0 and the associated α* > 1 at p* ≈ 0.4916; if the polynomial is non-negative there, or if a simulation reveals that GECA or BECA queries an edge more than once, the stated p* bound fails.

Watch

Extended reading notes

Core claim

The paper's central claim, Theorem 1.1, is that p_c < 1/2 − ε for some ε > 0, and the proof yields the quantitative bound p_c ≤ p* with p* ≈ 0.4916. The discovery is that the existence of a triangulation can be witnessed by a local ear-clipping search: the greedy algorithm GECA maintains a list of boundary vertices, shortening it by one when the edge closing an ear is present (probability p) and lengthening it by one otherwise (probability q = 1 − p). The list length therefore runs as a biased random walk, and the classical gambler's ruin formula bounds the chance that the walk never reaches a success state. A refined decision gadget, BECA, allows the list length to change by −2, −1, 0, +1,

Load-bearing premise

The Markov property of the ear-clipping algorithms relies on each edge being queried at most once, so consecutive steps are independent Bernoulli(p) trials; the paper asserts this as 'easy to see' but does not prove it, and the gambler's ruin analysis depends on it.

Editorial extensions

If this is right

For p > p*, with high probability the random edge set on the convex n-gon contains a triangulation, so most configurations of internal edges contain one.
The GECA variant gives a linear-time algorithm that actually constructs a triangulation whenever p > 1/2; the same exploration logic underlies the improved bound.
The new upper bound is strictly below the oriented percolation threshold, showing that the long-range correlations in the Catalan dynamics do not force the threshold up to the percolation scale.
The paper's own numerics and remarks suggest the true threshold is much lower, perhaps near 0.4, so the p* bound is still not expected to be sharp.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the GECA independence claim is asserted but not proved, a careful proof of the 'each edge queried once' property would close the only gap between the gambler's ruin picture and the formal argument.
Expanding the BECA decision tree to look at larger local neighbourhoods should yield a decreasing sequence of upper bounds converging to the true threshold; the drift calculation would need to be redone for each expansion.
The threshold may coincide with the infection threshold for Catalan percolation dynamics, so the same ear-clipping analysis can be read as a proof that information spreads past density 1/2 in that transitive closure process.
A finite-n simulation of GECA/BECA failure probability as a function of p would directly test the gambler's ruin prediction: the decay should scale as n^{−δ log α*}, with α* determined by the drift, which could be checked empirically.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Your reader's report is about right. The headline result—p_c ≤ p* ≈ 0.4916, breaking the 1/2 barrier—is new, and the ear-clipping/lookahead strategy is the right kind of simple idea. I think the GECA argument for p_c ≤ 1/2 is basically sound: the list length evolves as a ±1 walk, and the claim that each edge is queried at most once is true (the last vertex never moves left, and the third-from-last only moves left into a region that has not been queried), though it deserves a proof rather than 'easy to see.'

The soft spot is exactly where your stress test lands: Section 5. BECA is specified by a figure, not by a formal description of the seven moves, their reveal orders, or their transition probabilities. The drift polynomial is simply stated. Worse, the Markov property is justified by a sentence that doesn't parse with the algorithm as I read it. A BECA step starts with a list ending at v; to decide whether an ear can be clipped, the search must reveal edges incident to v or to vertices at or to the left of v. The text instead says the step depends only on adjacencies between vertices right of v but left of u and vertices right of u. That would be true for a step that only checks edges from the new region, but not for the clipping decision at the head of the list. If the revealed edge sets can overlap across steps, the increments are not independent Bernoulli trials and the gambler's-ruin bounds don't apply. Since BECA is the only ingredient that pushes below 1/2, this is load-bearing, not cosmetic.

I want to be clear: this is not a fatal flaw in the sense of the result being wrong. The drift computation is explicit and the polynomial has the claimed root. The gap is in the formal specification and the proof of the Markov property. It is eminently fixable by writing out the decision tree, proving that the revealed edges are disjoint across steps, and then the same gambler's-ruin analysis goes through. Similarly, the root-finding and completion phases are sketched with 'with high probability' but no constants; that is standard and likely fine, but it needs to be written out.

Who gets value: researchers in percolation, weak saturation, and random graph thresholds. The Catalan percolation connection to oriented percolation is cited correctly. This is not a paper to desk-reject; it is a serious contribution with a correct-looking core and an under-specified proof. My recommendation: send it to a good probability journal, ask for a major revision, and require a formal description of BECA and a rigorous verification of the Markov property.

Referee Report

3 major / 4 minor

Summary. The paper studies the random graph model on a convex n-gon in which every non-boundary diagonal is present independently with probability p, and asks for the threshold p_c at which a triangulation of the polygon appears with positive limiting probability. The main result, Theorem 1.1, asserts that p_c < 1/2 - epsilon for some epsilon > 0, with the quantitative bound p_c <= p* approximately 0.4916. The proof is algorithmic: the authors define a greedy ear-clipping algorithm (GECA) and show by a gambler's-ruin analysis that it triangulates with high probability for every p > 1/2, yielding p_c <= 1/2. They then introduce a more flexible 'better ear-clipping algorithm' (BECA), compute a negative drift for its list length at all p > p*, and conclude p_c <= p* via the generalized gambler's ruin bounds of Feller.

Significance. If the proof can be made fully rigorous, the result is a genuine quantitative improvement over the previous non-quantitative upper bound p_c < p_c^o, where p_c^o is the oriented percolation threshold (approximately 0.7055). The approach is elementary and self-contained, and the claimed bound p* ~ 0.4916 is consistent with numerical conjectures around 0.4. The negative-drift computation is explicit and not obtained by fitting, which is a definite strength. However, the central BECA argument is currently presented through a figure and a few informal sentences; the Markov property and transition probabilities are not formally specified. The paper is thus a promising contribution whose main theorem is not yet verifiable as written.

major comments (3)

[§5, Figure 4] BECA is not formally defined. The text says 'as depicted in Figure 4' and that the algorithm 'reveals some adjacencies in a certain order' and 'does one of 7 moves', but neither the seven moves nor their revealment orders, nor the resulting list updates, nor the transition probabilities are written down. The drift polynomial Delta is asserted directly from the figure. Since Theorem 1.1 rests entirely on this drift, the manuscript must provide a formal specification (pseudocode or transition table) from which Delta can be derived.
[§5, Markov property paragraph] The claimed Markov property for BECA is not proved and, as stated, is not convincing. The sentence 'the kth step depends only on adjacencies ... between the set vertices to the right of v but to the left of u and the set vertices to the right of u and including u itself' does not account for clipping decisions that involve the current list near its left end, and it may be ill-defined when the list length decreases. What is needed is a precise revealment protocol showing that every edge of E_{n,p} is queried at most once and that the transition probabilities of the induced chain on list length are time- and position-homogeneous. This is load-bearing: without it, the gambler's-ruin bounds of Section 2 do not apply.
[§4, Proof of Proposition 4.1] The GTA proof is only sketched. The statements 'there will be, with high probability, Omega(n/log n) many opportunities to find a root rho' and 'a simple union bound over at most 2J+b iterations' need a formal regeneration argument and a precise treatment of the completion phase. In particular, the dependencies between successive GECA runs and the events used to find rho are not analyzed. Since the proof of Theorem 1.1 says that it follows the same lines with BECA replacing GECA, these gaps propagate to the main theorem and must be filled.

minor comments (4)

[§4] Typographical errors: 'gamber's ruin' and 'end our of tour' should be corrected.
[§5] The statement 'Delta < 0 for all p > p*, where p* approximately 0.4916' is informal. Since Theorem 1.1 only requires existence of some p < 1/2 with Delta < 0, the authors could either give a rigorous rational interval for p* or simply use continuity of Delta at p = 1/2.
[§4] The constants delta and beta in the buffer construction are introduced informally. The conditions needed for the proof (e.g., delta sufficiently large relative to log(p/q), beta sufficiently small) should be stated explicitly.
[§5] The sentence 'by Figure 4, we see that ...' should be replaced by a reference to a formal algorithm definition, as noted in the major comments.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: derivation is self-contained, using standard gambler's ruin bounds and explicit ear-clipping algorithms.

full rationale

The central claim p_c <= p* (approx 0.4916) is established by defining explicit algorithms GECA and BECA and upper-bounding the probability that they fail to find a triangulation, using Feller's gambler's ruin estimates. The BECA transition probabilities are read from the decision tree in Figure 4; the drift polynomial Delta is an algebraic consequence of the seven listed moves, not a parameter fitted to data or to the claimed threshold. No step reduces by construction to its own input: p_c is defined independently (as a threshold for existence of any triangulation), and the algorithms provide a sufficient condition rather than a restatement. Prior self-citations ([2,10]) are used for context and to note the equivalence between Catalan percolation and triangulations, but Theorem 1.1's proof relies on the new algorithms and the standard external gambler's ruin bounds. The Markov property of BECA is asserted somewhat informally, and the decision tree is under-specified in the text, but these are rigor/verification concerns, not circularity: even a gap there would not make the conclusion equivalent to the input. No fitted quantity is renamed as a prediction.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new physical or mathematical entities; GECA and BECA are algorithms, not postulates. The proof rests on standard gambler's ruin theory and polygonal triangulation facts, plus two proof constants delta and beta that are not part of the final theorem. No fitted parameters enter the central claim.

free parameters (2)

delta
A large positive constant used to define the list-length cap J = delta log n in the proof of Proposition 4.1. It is chosen to make the probability n^{1 - delta log(p/q)} tend to 0, not fitted to data.
beta
A small positive constant used to set the buffer size b = beta log n. It is chosen as a proof parameter to balance root-finding success probability with the final union bound, not fitted to data.

assumptions (3)

standard math Gambler's ruin bounds from Feller (sequential sampling) give explicit upper and lower bounds on the probability that a negatively drifted random walk with bounded jumps hits a jackpot before ruin.
Invoked in Section 2 (equation 1) and used in both Proposition 4.1 and Theorem 1.1 to control the probability that a list reaches length J.
standard math A convex polygon can be triangulated by repeatedly clipping ears, and the resulting triangulation covers the polygon.
Used in the definitions of GECA and BECA and in the completion step of the triangulation algorithm; a standard fact in polygonal decomposition.
domain assumption The present diagonal edges E_{n,p} are independent Bernoulli(p) random variables.
This is the model definition from Section 1; independence is essential for computing step probabilities as products of p and q.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the threshold for triangulations inside convex polygons." pith.science (2026). https://pith.science/paper/DGL7XKCU

@misc{pith2026250910160,
  author       = {Pith},
  title        = {Pith review of: On the threshold for triangulations inside convex polygons},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DGL7XKCU}},
  note         = {Machine review of arXiv:2509.10160}
}

abstract

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=\Theta(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.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

14 extracted references · 1 linked inside Pith

[1]

Aizenman and G

M. Aizenman and G. Grimmett,Strict monotonicity for critical points in percolation and ferromagnetic models, J. Statist. Phys.63(1991), no. 5-6, 817–835

1991
[2]

Archer, I

E. Archer, I. Hartarsky, B. Kolesnik, S. Olesker-Taylor, B. Schapira, and D. Valesin, Catalan percolation, Probab. Theory Related Fields, Special Issue: In Celebration of Geoffrey Grimmett’s 70th Birthday, to appear, preprint available at arXiv:2404.19583

arXiv
[3]

Balogh, B

J. Balogh, B. Bollobás, and R. Morris,Graph bootstrap percolation, Random Structures Algorithms41(2012), no. 4, 413–440

2012
[4]

Bollobás,Weakly k-saturated graphs, Beiträge zur Graphentheorie (Kolloquium, Manebach, 1967), B

B. Bollobás,Weakly k-saturated graphs, Beiträge zur Graphentheorie (Kolloquium, Manebach, 1967), B. G. Teubner Verlagsgesellschaft, Leipzig, 1968, pp. 25–31

1967
[5]

Bollobás and A

B. Bollobás and A. M. Frieze,Spanning maximal planar subgraphs of random graphs, Random Structures Algorithms2(1991), no. 2, 225–231

1991
[6]

R., Kozma, G., and Sidoravicius, V .,Brochette percola- tion, Israel J

Duminil-Copin, H., Hilário, M. R., Kozma, G., and Sidoravicius, V .,Brochette percola- tion, Israel J. Math.225(2018), no. 1, 479–501

2018
[7]

Durrett,Oriented percolation in two dimensions, Ann

R. Durrett,Oriented percolation in two dimensions, Ann. Probab.12(1984), no. 4, 999–1040

1984
[8]

J. W. Essam, A. J. Guttmann, and K. De’Bell,On two-dimensional directed percolation, J. Phys. A21(1988), no. 19, 3815–3832

1988

Show all 14 references

[9]

Feller,An introduction to probability theory and its applications

W. Feller,An introduction to probability theory and its applications. Vol. I, third ed., John Wiley & Sons, Inc., New York-London-Sydney, 1968. 12 B. KOLESNIK, G. ZAKHAROV, AND M. ZHUKOVSKII

1968
[10]

Gravner and B

J. Gravner and B. Kolesnik,Transitive closure in a polluted environment, Ann. Appl. Probab.33(2023), no. 1, 107–126

2023
[11]

Gravner and E

J. Gravner and E. McDonald,Bootstrap percolation in a polluted environment, J. Statist. Phys.87(1997), no. 3-4, 915–927

1997
[12]

J. Kahn, B. Narayanan, and J. Park,The threshold for the square of a Hamilton cycle, Proc. Amer. Math. Soc.149(2021), no. 8, 3201–3208

2021
[13]

Riordan,Spanning subgraphs of random graphs, Combinatorics, Probability & Computing9(2000), no

O. Riordan,Spanning subgraphs of random graphs, Combinatorics, Probability & Computing9(2000), no. 2, 125–148

2000
[14]

Zhukovskii,Sharp thresholds for spanning regular subgraphs, preprint available at arXiv:2502.14794

M. Zhukovskii,Sharp thresholds for spanning regular subgraphs, preprint available at arXiv:2502.14794

arXiv

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [1]

Aizenman and G

M. Aizenman and G. Grimmett,Strict monotonicity for critical points in percolation and ferromagnetic models, J. Statist. Phys.63(1991), no. 5-6, 817–835

1991

[2] [2]

Archer, I

E. Archer, I. Hartarsky, B. Kolesnik, S. Olesker-Taylor, B. Schapira, and D. Valesin, Catalan percolation, Probab. Theory Related Fields, Special Issue: In Celebration of Geoffrey Grimmett’s 70th Birthday, to appear, preprint available at arXiv:2404.19583

arXiv

[3] [3]

Balogh, B

J. Balogh, B. Bollobás, and R. Morris,Graph bootstrap percolation, Random Structures Algorithms41(2012), no. 4, 413–440

2012

[4] [4]

Bollobás,Weakly k-saturated graphs, Beiträge zur Graphentheorie (Kolloquium, Manebach, 1967), B

B. Bollobás,Weakly k-saturated graphs, Beiträge zur Graphentheorie (Kolloquium, Manebach, 1967), B. G. Teubner Verlagsgesellschaft, Leipzig, 1968, pp. 25–31

1967

[5] [5]

Bollobás and A

B. Bollobás and A. M. Frieze,Spanning maximal planar subgraphs of random graphs, Random Structures Algorithms2(1991), no. 2, 225–231

1991

[6] [6]

R., Kozma, G., and Sidoravicius, V .,Brochette percola- tion, Israel J

Duminil-Copin, H., Hilário, M. R., Kozma, G., and Sidoravicius, V .,Brochette percola- tion, Israel J. Math.225(2018), no. 1, 479–501

2018

[7] [7]

Durrett,Oriented percolation in two dimensions, Ann

R. Durrett,Oriented percolation in two dimensions, Ann. Probab.12(1984), no. 4, 999–1040

1984

[8] [8]

J. W. Essam, A. J. Guttmann, and K. De’Bell,On two-dimensional directed percolation, J. Phys. A21(1988), no. 19, 3815–3832

1988