pith. sign in

arxiv: 2605.02067 · v2 · pith:XHERDWKRnew · submitted 2026-05-03 · 🧮 math.CO · cs.CG· cs.DM· cs.DS

Faster Mixing for Triangulations via Transport Flows

Vedat Levi Alev , Daniel Frishberg , Michail Sarantis , Prasad Tetali This is my paper

Pith reviewed 2026-05-08 19:05 UTC · model grok-4.3

classification 🧮 math.CO cs.CGcs.DMcs.DS
keywords triangulation flip chainmixing timetransport flowsrelaxation timelog-Sobolev inequalityMarkov chainsconvex polygons
0
0 comments X

The pith

The triangulation flip chain on a convex (n+2)-gon mixes in Õ(n²) time.

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

This paper proves that the Markov chain generated by randomly flipping diagonals in a triangulation of a convex polygon reaches a uniform random triangulation after Õ(n²) steps. The bound holds for both the relaxation time, which governs the spectral gap, and the log-Sobolev time, which controls concentration. The prior best upper bound was Õ(n³), so the new result narrows the distance to the known lower bound of Ω(n^{3/2}). The argument refines the transport-flows technique to extract tighter functional inequalities directly from the combinatorial decomposition of all triangulations.

Core claim

We prove an Õ(n²) bound for the relaxation time and the log-Sobolev time (inverse log-Sobolev constant) of the classical triangulation flip chain on a convex (n+2)-gon, implying a mixing time of Õ(n²). The previous state of the art for the mixing time of this chain, due to Eppstein and Frishberg, was Õ(n³), while the best known lower bound on the mixing time, due to Molloy, Reed, and Steiger, is Ω(n^{3/2}). Our relaxation time bound makes significant progress towards Aldous' conjectured bound of Θ(n^{3/2}) for the relaxation time. We improve upon the analysis of Eppstein and Frishberg by further developing the framework of transport flows introduced in the work of Chen et al.

What carries the argument

Transport flows constructed on a combinatorial decomposition of the space of all triangulations, used to bound the Dirichlet form and obtain Poincaré and log-Sobolev inequalities for the flip chain.

If this is right

  • The mixing time of the flip chain is at most Õ(n²).
  • The log-Sobolev constant is at least the reciprocal of Õ(n²).
  • The analysis advances toward the conjectured Θ(n^{3/2}) relaxation time.
  • Combinatorial decompositions can be used more efficiently to derive functional inequalities for other Markov chains.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same transport-flow refinement may yield quadratic bounds for flip chains on triangulations of other convex surfaces.
  • If the hidden constants are moderate, practical algorithms for uniform sampling could safely run for far fewer than the previously proven cubic number of steps.
  • Tighter control on the flow costs might eventually close the remaining gap to the n^{3/2} lower bound.

Load-bearing premise

The transport flows can be built from the decomposition so that their total cost is at most quadratic in n, without hidden polynomial factors that would spoil the bound.

What would settle it

An explicit set S of triangulations for which the total flow cost out of S exceeds the quadratic allowance by more than a constant factor would invalidate the claimed relaxation-time bound.

Figures

Figures reproduced from arXiv: 2605.02067 by Daniel Frishberg, Michail Sarantis, Prasad Tetali, Vedat Levi Alev.

Figure 1
Figure 1. Figure 1: The original polygon is decomposed into three polygons by view at source ↗
Figure 2
Figure 2. Figure 2: Left: the set Ωi ⊆ Ω, represented by the state i ∈ Ωˆ, is the set of all triangulations that contain the triangle shown in the figure. Center: the set Ωj is defined similarly. Right: The set Ωij ⊆ Ωi (see the definition of pinnings) is the set of triangulations that contain the two triangles shown in the figure. The central triangle t partitions the polygon into three smaller polygons (one of which may be … view at source ↗
Figure 3
Figure 3. Figure 3: A triangulation in Ωtt′ must necessarily contain the triangles t and u := ijb. Given a triangulation in Ω(2) t and Ω(3) t (light blue), we are left with triangulations in Ω(1) t (orange) subject to containing u (shaded orange). We can now think as simply discarding polygons (2), (3). Then, we set the side of t ∩ (1) as the special edge of polygon (1), and such triangulations of (1) correspond to the elemen… view at source ↗
Figure 4
Figure 4. Figure 4: A pinning η = (i1, i2, i3, i4) and the corresponding sequence of triangles. Given a pinning η = (i1, i2, . . . , ik), let πˆ(η) = π(Ωη). Given a vertex j ∈ Ωˆ η,l ∪ Ωˆ η,r, let ηj be the pinning (i1, i2, . . . , ik, j). In general, writing a string of pinnings and/or vertices will denote the pinning derived by concatenating the elements of the string. E.g. Ωijk where i, j, k ∈ Ωˆ is equivalent to Ωη where … view at source ↗
Figure 5
Figure 5. Figure 5: A pinning η = (i1, i2, i3, i4). The untriangulated region is shown with a fill. i3 i4 i3 i4 i3 + 1 i3 + 2 i3 + 1 ≡ i3 + 2 ≡ view at source ↗
Figure 6
Figure 6. Figure 6: For the pinning of view at source ↗
Figure 7
Figure 7. Figure 7: When η := (i1) and j := i1 + 1, πˆη(j) equals the proportion of triangulations of the orange region that contain the shaded triangle. This is the ratio of two consecutive Catalan numbers. When η ′ = (i1, i2) with i2 := i1 + 2, the triangle i1ji2 is always contained, so ˆπη′ (j) = 1. Similarly πˆη′ (s) = CaCl−a−2 Cl−1 , and πˆη′ (t) = Ca−1Cl−a−1 Cl−1 , where l + 1 > k + 1 is the number of sides of P. Theref… view at source ↗
Figure 8
Figure 8. Figure 8: Two triangulations x, y ∈ Ωη, where η = ηxy = (k1, k2, k3, kd). depth level d we have X η:x∈Ωη,d(η)=d |ϕ (x) ij,η| ≤ 1 . That is, the sum of the congestion values incurred in the flow in Theorem 5.1 across flips at a given level of (the dual tree of) a given triangulation x ∈ Ωi sums to at most one. Formally: Lemma 6.2. With the notation of Theorem 5.1, given i, j ∈ Ωˆ and given η = (k1 = i, k2, . . . , kd… view at source ↗
Figure 9
Figure 9. Figure 9: A triangulation x ∈ Ω, with a pinning η = (k1, . . . , kd) indicated such that x ∈ Ωη. Here we have x ∈ Ωη(l) and x ∈ Ωη(r) where η (l) = ηk(l) d+1 = ηk(l) 6 and similarly x ∈ Ωη(r) where η (r) = ηk(r) 6 . Roughly speaking, this will, with some algebraic manipulation, enable the shaving of a Θ(√ n) factor from our overall average congestion bound. More precisely, we will use Theorem 6.6 to prove Theorem 5.… view at source ↗
Figure 10
Figure 10. Figure 10: Elements and non-elements of Tij . Given a pinning η and a vertex j /∈ η, let j ∼ η if j ∈ Ωˆ η,l or j ∈ Ωˆ η,r. Given t ∈ Tij , let η ∼ t if j ∼ η and η contains the side of t opposite to j. Then: Lemma 6.6. Let i, j ∈ Ωˆ. Let t ∈ Tij and η = (i, k2, k3, . . . , kd) be a pinning in Ωˆ i such that j ∼ η and η ∼ t. Then, there exist constants C, c > 0 such that if n is sufficiently large then 28 view at source ↗
Figure 11
Figure 11. Figure 11: t is a triangle in Tij . Given a triangulation x ∈ Ωi containing t, we recover the pinning η : x ∈ Ωηj by considering the dual graph of the triangulation. The triangles of η correspond to the vertices of the (unique) path from (0, n + 1, i) to t (excluded). li(t) is the size of the orange polygon. X x∈Ωηj ,y∈Ωη |ϕij,xy|π(x)P(x, y) ≤ C logc n p ui(t) ∆ · πˆ(η)ˆπ(j). Proof. Let x ∗ denote the dual tree of a… view at source ↗
Figure 12
Figure 12. Figure 12: An illustration of Theorem B.1: in this example, η = (k1, k2, k3, k4); we have s, t ∈ Ωη,r and t < s < k4; and therefore either 0 ≤ ϕij,ηs ≤ ϕij,ηt or 0 ≥ ϕij,ηs ≥ ϕij,ηt. (i) Pt,t′ = (Ωtt′ , Ωt ′t, σtt′ , δtt′ ) where σtt′ = Oe( √ n). (ii) Pt,k = {(S (t,η) k , Ωt, σk, δk)} or Pt,k = {(Ωt, S(t,η) k , σk, δk)} where S (t,η) k = S i∈S Ω (η) ti for some S ⊆ Ωˆ(t,η) , where η ∈ Ω (1) t × Ω (2) t or η ∈ Ω (2) … view at source ↗
read the original abstract

We prove an $\widetilde O(n^2)$ bound for the relaxation time and the log-Sobolev time (inverse log-Sobolev constant) of the classical triangulation flip chain on a convex $(n+2)$-gon, implying a mixing time of $\widetilde O(n^2)$. The previous state of the art for the mixing time of this chain, due to Eppstein and Frishberg, was $\widetilde O(n^3)$, while the best known lower bound on the mixing time, due to Molloy, Reed, and Steiger, is $\Omega(n^{3/2})$. Our relaxation time bound makes significant progress towards Aldous' conjectured bound of $\Theta(n^{3/2})$ for the relaxation time. We improve upon the analysis of Eppstein and Frishberg by further developing the framework of transport flows introduced in the work of Chen et al. In this light, our results can be seen as a more efficient way of using combinatorial decompositions to obtain functional inequalities for Markov chains. We hope our ideas will find other applications in the future.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript proves an Õ(n²) upper bound on the relaxation time and the log-Sobolev time (inverse log-Sobolev constant) of the classical triangulation flip chain on triangulations of a convex (n+2)-gon. This yields a mixing time of Õ(n²) and improves the prior Õ(n³) bound of Eppstein and Frishberg while approaching Aldous' conjectured Θ(n^{3/2}) relaxation time. The argument refines the transport-flows framework of Chen et al. by supplying an explicit recursive combinatorial decomposition of the triangulation space together with a flow that routes mass along controlled flip paths.

Significance. If correct, the result constitutes clear progress on a well-studied mixing-time problem for a combinatorially natural Markov chain. The explicit use of the Catalan recursive structure to obtain congestion and cost bounds of O(n² polylog n) for both the Dirichlet form and entropy decay is a methodological strength that may transfer to other recursively decomposable state spaces. The work also supplies a concrete example of how transport flows can be instantiated without introducing hidden n-dependent factors that would spoil the claimed scaling.

major comments (1)
  1. [§3] §3 (transport-flow construction): the congestion and path-length bounds derived from the recursive decomposition must be stated as an explicit lemma (with the precise polylog factors) before invoking the Chen et al. framework; without this, it is impossible to confirm that the resulting relaxation-time and log-Sobolev-time bounds are truly Õ(n²) rather than Õ(n² log^c n) for some c that would affect the final claim.
minor comments (2)
  1. [Theorem 1.1] The statement of the main theorem should include a short sentence recalling the precise relationship between relaxation time, log-Sobolev time, and mixing time that is being used (including any absolute constants).
  2. [Introduction] A one-sentence clarification of the precise meaning of “convex (n+2)-gon” (i.e., the number of vertices and the role of the two fixed boundary edges) would prevent minor confusion for readers unfamiliar with the triangulation literature.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and constructive comment. We agree that the transport-flow bounds should be stated explicitly and have revised the manuscript accordingly to strengthen the presentation.

read point-by-point responses

  1. Referee: §3 (transport-flow construction): the congestion and path-length bounds derived from the recursive decomposition must be stated as an explicit lemma (with the precise polylog factors) before invoking the Chen et al. framework; without this, it is impossible to confirm that the resulting relaxation-time and log-Sobolev-time bounds are truly Õ(n²) rather than Õ(n² log^c n) for some c that would affect the final claim.

    Authors: We agree with the referee that an explicit lemma is needed for clarity and to allow direct verification of the claimed scaling. In the revised manuscript we have added Lemma 3.1, which states that the recursive decomposition yields a transport flow with congestion O(n² log² n) and average path length O(n log n). These bounds follow from a direct counting argument on the number of flips along the canonical paths in the Catalan recursion and the multiplicity of each edge in the flow. Substituting these explicit quantities into the Chen et al. transport-flow theorem immediately produces relaxation and log-Sobolev times of O(n² log³ n), which is absorbed into the stated Õ(n²) notation. No further hidden n-dependent factors arise. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via external framework and explicit construction

full rationale

The paper derives the Õ(n²) relaxation and log-Sobolev bounds by instantiating the transport-flows framework of Chen et al. on an explicit recursive decomposition of triangulations together with a flow routing mass along flip paths whose congestion and cost are controlled by Catalan numbers and path lengths. This construction is presented as independent of the target bound and does not reduce any prediction to a fitted parameter or self-referential definition. The citation to Eppstein-Frishberg (prior work by one co-author) is used only to state the previous Õ(n³) bound and is not load-bearing for the new argument. No self-definitional steps, ansatz smuggling, or uniqueness theorems imported from the authors' own prior work appear in the derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on standard Markov chain theory and the applicability of transport flows to polygon triangulations; no free parameters or invented entities are visible in the abstract.

axioms (1)
  • standard math Functional inequalities (relaxation time, log-Sobolev) apply to the flip chain and can be bounded via transport flows.
    Invoked to convert combinatorial decompositions into time bounds.

pith-pipeline@v0.9.0 · 5515 in / 1287 out tokens · 77036 ms · 2026-05-08T19:05:14.502073+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Burnside process on parking functions and Dyck paths

    math.PR 2026-05 unverdicted novelty 7.0

    Burnside processes on parking functions and Dyck paths mix in O(n log n) time, yielding approximate uniform sampling algorithms for increasing parking functions, Dyck paths, and polygon triangulations.

  2. On weighted partial triangulations of convex polygons

    cs.DM 2026-05 unverdicted novelty 6.0

    A randomized algorithm exactly samples weighted partial triangulations of convex polygons in expected O((n sqrt(lambda) + 1) log n) time for large n.