pith. machine review for the scientific record. sign in

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

Recognition: 3 theorem links

· Lean Theorem

Faster Mixing for Triangulations via Transport Flows

Vedat Levi Alev , Daniel Frishberg , Mihalis Sarantis , Prasad Tetali
Authors on Pith no claims yet

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, Mihalis 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 \emph{relaxation time} and the \emph{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 \emph{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.

Reference graph

Works this paper leans on

65 extracted references · 15 canonical work pages · 1 internal anchor

  1. [1]

    50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , year =

    Eppstein, David and Frishberg, Daniel , title =. 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , year =

    2023

  2. [2]

    arXiv preprint , year =

    Eppstein, David and Frishberg, Daniel , title =. arXiv preprint , year =

  3. [3]

    2010.16158 , archivePrefix=

    Marc Heinrich , year=. 2010.16158 , archivePrefix=

    work page arXiv 2010

  4. [4]

    Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =

    Zongchen Chen , title =. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =. 2024 , doi =

    2024

  5. [5]

    34th International Symposium on Algorithms and Computation (ISAAC 2023) , year =

    Eppstein, David and Frishberg, Daniel , title =. 34th International Symposium on Algorithms and Computation (ISAAC 2023) , year =

    2023

  6. [6]

    Cambrian lattices , author=. Adv. Math. , volume=. 2006 , pages=

    2006

  7. [7]

    2003 , pages=

    Fomin, Sergey and Zelevinsky, Andrei , journal=. 2003 , pages=

    2003

  8. [8]

    arXiv preprint math/0505518 , year=

    Root systems and generalized associahedra , author=. arXiv preprint math/0505518 , year=

    work page internal anchor Pith review arXiv

  9. [9]

    European Journal of Combinatorics , volume=

    The diameter of type D associahedra and the non-leaving-face property , author=. European Journal of Combinatorics , volume=. 2016 , publisher=

    2016

  10. [12]

    , title =

    Aldous, David J. , title =. 2000 , issue_date =. doi:10.1017/S096354830000417X , journal =

    work page doi:10.1017/s096354830000417x 2000

  11. [13]

    , title =

    Aldous, David J. , title =

  12. [14]

    Tetali , booktitle=

    Lisa McShine and P. Tetali , booktitle=. On the mixing time of the triangulation walk and other

  13. [15]

    Combinatorics, Probability and Computing , volume=

    Intersection Conductance and Canonical Alternating Paths: Methods for General Finite Markov Chains , author=. Combinatorics, Probability and Computing , volume=. 2014 , publisher=

    2014

  14. [16]

    On the Mixing Rate of the Triangulation Walk , journal =

    Molloy, Michael and Reed, Bruce and Steiger, William , year =. On the Mixing Rate of the Triangulation Walk , journal =

  15. [17]

    Annals of Applied Probability , year=

    Random lattice triangulations: structure and algorithms , author=. Annals of Applied Probability , year=

  16. [18]

    Probability Theory and Related Fields , year=

    Caraceni, Alessandra and Stauffer, Alexandre , title=. Probability Theory and Related Fields , year=

  17. [19]

    Balanced matroids , year =

    Feder, Tom\'. Balanced matroids , year =. doi:10.1145/129712.129716 , booktitle =

    work page doi:10.1145/129712.129716

  18. [20]

    SIAM journal on computing , volume=

    Approximating the permanent , author=. SIAM journal on computing , volume=. 1989 , publisher=

    1989

  19. [21]

    2025 , eprint=

    Faster Mixing of the Jerrum-Sinclair Chain , author=. 2025 , eprint=

    2025

  20. [22]

    Alexandre Stauffer , journal=. A. 2015 , volume=

    2015

  21. [23]

    Faster Mixing via Average Conductance , year =

    Lov\'. Faster Mixing via Average Conductance , year =. doi:10.1145/301250.301317 , booktitle =

    work page doi:10.1145/301250.301317

  22. [24]

    2017 , publisher=

    Markov Chains and Mixing Times: Second Edition , author=. 2017 , publisher=

    2017

  23. [25]

    1988 , publisher =

    Jerrum, Mark and Sinclair, Alistair , title =. 1988 , publisher =. doi:10.1145/62212.62234 , booktitle =

    work page doi:10.1145/62212.62234 1988

  24. [26]

    2019 , publisher =

    Anari, Nima and Liu, Kuikui and Gharan, Shayan Oveis and Vinzant, Cynthia , title =. 2019 , publisher =. doi:10.1145/3313276.3316385 , booktitle =

    work page doi:10.1145/3313276.3316385 2019

  25. [27]

    2023 , eprint=

    Lecture Notes on Spectral Independence and Bases of a Matroid: Local-to-Global and Trickle-Down from a Markov Chain Perspective , author=. 2023 , eprint=

    2023

  26. [28]

    Efthymiou, Charilaos and Hayes, Thomas P. and. Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees , booktitle =. 2023 , publisher =

    2023

  27. [29]

    SIAM Journal on Computing , year =

    Chen, Zongchen and Liu, Kuikui and Vigoda, Eric , title =. SIAM Journal on Computing , year =

  28. [30]

    Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model , year=

    Anari, Nima and Liu, Kuikui and Gharan, Shayan Oveis , booktitle=. Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model , year=

  29. [31]

    2020 , publisher =

    Alev, Vedat Levi and Lau, Lap Chi , title =. 2020 , publisher =. doi:10.1145/3357713.3384317 , booktitle =

    work page doi:10.1145/3357713.3384317 2020

  30. [32]

    The Sharpest Cut: The Impact of Manfred Padberg and His Work , pages=

    On the expansion of graphs of 0/1-polytopes , author=. The Sharpest Cut: The Impact of Manfred Padberg and His Work , pages=. 2004 , publisher=

    2004

  31. [33]

    2020 , publisher =

    Kaufman, Tali and Oppenheim, Izhar , title =. 2020 , publisher =. doi:10.1007/s00493-019-3847-0 , journal =

    work page doi:10.1007/s00493-019-3847-0 2020

  32. [34]

    2007 , publisher =

    Eppstein, David , title =. 2007 , publisher =. doi:10.1145/1247069.1247084 , booktitle =

    work page doi:10.1145/1247069.1247084 2007

  33. [35]

    2013 , publisher =

    Caputo, Pietro and Martinelli, Fabio and Sinclair, Alistair and Stauffer, Alexandre , title =. 2013 , publisher =. doi:10.1145/2488608.2488685 , series =

    work page doi:10.1145/2488608.2488685 2013

  34. [36]

    Probability Theory and Related Fields , year=

    Stauffer, Alexandre , title=. Probability Theory and Related Fields , year=. doi:10.1007/s00440-016-0735-z , url=

    work page doi:10.1007/s00440-016-0735-z

  35. [37]

    Analyzing Glauber dynamics by comparison of Markov chains

    Randall, Dana and Tetali, Prasad. Analyzing Glauber dynamics by comparison of Markov chains. LATIN'98: Theoretical Informatics. 1998

    1998

  36. [38]

    Elementary Bounds on

    Mark Jerrum and Jung-Bae Son and Prasad Tetali and Eric Vigoda , journal =. Elementary Bounds on

  37. [39]

    The Annals of Applied Probability , volume=

    Logarithmic Sobolev inequalities for finite Markov chains , author=. The Annals of Applied Probability , volume=. 1996 , publisher=

    1996

  38. [40]

    The Annals of Applied Probability , number =

    Persi Diaconis and Daniel Stroock , title =. The Annals of Applied Probability , number =. 1991 , doi =

    1991

  39. [41]

    Combinatorics, Probability and Computing , publisher=

    Sinclair, Alistair , year=. Combinatorics, Probability and Computing , publisher=. doi:10.1017/S0963548300000390 , number=

    work page doi:10.1017/s0963548300000390

  40. [42]

    The Annals of Applied Probability , volume=

    Modified log-Sobolev inequalities for strong-Rayleigh measures , author=. The Annals of Applied Probability , volume=. 2023 , publisher=

    2023

  41. [43]

    Chung, F. R. K. and Tetali, Prasad , year=. Isoperimetric Inequalities for. doi:10.1017/S0963548397003350 , journal=

    work page doi:10.1017/s0963548397003350

  42. [44]

    The Annals of Applied Probability , publisher =

    Persi Diaconis and Laurent Saloff-Coste , title =. The Annals of Applied Probability , publisher =. 1993 , doi =

    1993

  43. [45]

    Electronic Journal of Combinatorics , volume=

    Cluster algebras of type D: pseudotriangulations approach , author=. Electronic Journal of Combinatorics , volume=

  44. [46]

    Combinatorics, Probability and Computing , author=

    The Distribution of Heights of Binary Trees and Other Simple Trees , DOI=. Combinatorics, Probability and Computing , author=

  45. [47]

    Canadian Journal of Mathematics , author=

    On the Altitude of Nodes in Random Trees , DOI=. Canadian Journal of Mathematics , author=

  46. [48]

    Lectures on finite

    Saloff-Coste, Laurent , booktitle=. Lectures on finite. 1997 , publisher=

    1997

  47. [49]

    Foundations and Trends

    Mathematical aspects of mixing times in Markov chains , author=. Foundations and Trends. 2006 , publisher=

    2006

  48. [50]

    2003 , doi =

    The Catalan matroid , journal =. 2003 , doi =

    2003

  49. [51]

    2016 , publisher=

    Problems in catalan mixing and matchings in regular hypergraphs , author=. 2016 , publisher=

    2016

  50. [52]

    The Annals of Applied Probability , year=

    Mixing times of lozenge tiling and card shuffling Markov chains , author=. The Annals of Applied Probability , year=

  51. [53]

    41st International Symposium on Computational Geometry (SoCG 2025) , year=

    Rapid Mixing of the Flip Chain over Non-Crossing Spanning Trees , author=. 41st International Symposium on Computational Geometry (SoCG 2025) , year=

    2025

  52. [54]

    Journal of Combinatorial Theory, Series B , volume=

    _1 , isoperimetric inequalities for graphs, and superconcentrators , author=. Journal of Combinatorial Theory, Series B , volume=. 1985 , publisher=

    1985

  53. [55]

    Problems in analysis , pages=

    A lower bound for the smallest eigenvalue of the Laplacian , author=. Problems in analysis , pages=. 2015 , publisher=

    2015

  54. [56]

    Combinatorica , volume=

    High order random walks: Beyond spectral gap , author=. Combinatorica , volume=. 2020 , publisher=

    2020

  55. [57]

    Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Entropic independence: optimal mixing of down-up random walks , author=. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  56. [58]

    Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Optimal mixing of Glauber dynamics: Entropy factorization via high-dimensional expansion , author=. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=

  57. [59]

    arXiv preprint arXiv:2012.14317 , year=

    Local-to-global contraction in simplicial complexes , author=. arXiv preprint arXiv:2012.14317 , year=

    work page arXiv 2012

  58. [60]

    Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Rapid mixing for colorings via spectral independence , author=. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2021 , organization=

    2021

  59. [61]

    ACM Transactions on Algorithms (TALG) , volume=

    Rapid mixing from spectral independence beyond the Boolean domain , author=. ACM Transactions on Algorithms (TALG) , volume=. 2022 , publisher=

    2022

  60. [62]

    The American Mathematical Monthly , volume=

    Triangulating the circle, at random , author=. The American Mathematical Monthly , volume=. 1994 , publisher=

    1994

  61. [63]

    and Knuth, Donald E

    Graham, Ronald L. and Knuth, Donald E. and Patashnik, Oren , title =. 1994 , publisher =

    1994

  62. [64]

    The Mathematical Intelligencer , year=

    Catalan Numbers, Their Generalization, and Their Uses , author=. The Mathematical Intelligencer , year=

  63. [65]

    Journal of the American Mathematical Society , volume=

    Rotation distance, triangulations, and hyperbolic geometry , author=. Journal of the American Mathematical Society , volume=

  64. [66]

    Available at:

    Lecture notes on expansion, sparsest cut, and spectral graph theory , author =. Available at:

  65. [67]

    Ford, L. R. jun. and Fulkerson, D. R. , title =. Can. J. Math. , issn =. 1956 , doi =

    1956