pith. sign in

arxiv: 2606.27545 · v1 · pith:AM4XDL7Tnew · submitted 2026-06-25 · 🧮 math.PR · cs.DS

A simple proof of rapid mixing on random regular graphs beyond uniqueness

Andreas G\"obel , Matthew Jenssen , Marcus Michelen , Marcus Pappik , Will Perkins , Leon Schiller This is my paper

Pith reviewed 2026-06-29 00:42 UTC · model grok-4.3

classification 🧮 math.PR cs.DS
keywords rapid mixingGlauber dynamicshard-core modelrandom regular graphsPoincaré inequalityBochner-Bakry-Émerytree uniqueness threshold
0
0 comments X

The pith

A Bochner-Bakry-Émery argument yields a short self-contained proof that Glauber dynamics mixes rapidly on random regular graphs past the tree uniqueness threshold.

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

The paper establishes a simple proof of rapid mixing for Glauber dynamics on the hard-core model defined on random regular graphs, even when the fugacity parameter lies beyond the tree uniqueness threshold. It achieves this by adapting a Bochner-Bakry-Émery technique originally developed for continuum spatial birth-and-death processes, directly deriving a Poincaré inequality without relying on prior local-to-global machinery. The argument expands the Dirichlet form in terms of the squared L2-norm of the generator applied to a test function and cancels a sum-of-squares remainder. A reader would care because the resulting proof is markedly shorter and self-contained while applying to the broader class of discrete distributions supported on downward-closed families.

Core claim

We give a short and self-contained proof via a Bochner-Bakry-Émery approach and directly show a Poincaré inequality by expanding the Dirichlet form in terms of the L²-norm of the generator applied to a test function and eliminating a sum of squares term. Our proof is a streamlined version of an argument of Kondratiev, Kuna, and Ohlerich used to study spatial birth-and-death dynamics for Gibbs point processes in the continuum, which we adapt to the discrete setting. This establishes rapid mixing for the hard-core model on random regular graphs beyond the uniqueness threshold.

What carries the argument

The adapted Bochner-Bakry-Émery method that expands the Dirichlet form of the Glauber dynamics generator and removes a sum-of-squares term to obtain the Poincaré inequality directly.

If this is right

  • Rapid mixing of Glauber dynamics holds for the hard-core model on random regular graphs at fugacities strictly above the tree uniqueness threshold.
  • The same short argument applies verbatim to any discrete distribution supported on a downward-closed set family.
  • The derived Poincaré inequality is obtained without invoking any local-to-global comparison theorems.
  • The method remains valid under the standard assumptions that guarantee the existence of the Glauber dynamics on the finite graph.

Where Pith is reading between the lines

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

  • The same expansion technique may simplify mixing-time proofs for other local Markov chains such as Metropolis-Hastings on the same state spaces.
  • Because the argument works uniformly for downward-closed families, it could be checked directly on the independent-set polytope of other sparse graphs.
  • The discrete-continuum parallel suggests that analogous Bochner-type identities might control mixing for spatial birth-and-death processes on random geometric graphs.

Load-bearing premise

The adaptation of the Kondratiev-Kuna-Ohlerich continuum argument to discrete Glauber dynamics on random regular graphs introduces no new technical obstacles or extra assumptions.

What would settle it

A concrete counter-example on a random regular graph beyond the uniqueness threshold in which the sum-of-squares term cannot be eliminated for some admissible test function, causing the derived Poincaré constant to fail to be positive.

read the original abstract

A recent breakthrough of Chen, Chen, Chen, Yin, and Zhang shows rapid mixing for Glauber dynamics for the hard-core model on random regular graphs beyond the tree uniqueness threshold. Their approach builds upon the literature of various local-to-global techniques and applies to a more general setting of discrete distributions supported on downward-closed set families. We give a short and self-contained proof via a Bochner--Bakry--\'{E}mery approach and directly show a Poincar\'e inequality by expanding the Dirichlet form in terms of the $L^2$-norm of the generator applied to a test function and eliminating a sum of squares term. Our proof is a streamlined version of an argument of Kondratiev, Kuna, and Ohlerich used to study spatial birth-and-death dynamics for Gibbs point processes in the continuum, which we adapt to the discrete setting.

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 / 1 minor

Summary. The manuscript presents a short, self-contained proof of rapid mixing for Glauber dynamics of the hard-core model on random regular graphs beyond the tree uniqueness threshold. It uses a Bochner-Bakry-Émery approach to establish a Poincaré inequality directly by expanding the Dirichlet form as an L²-norm of the generator applied to a test function and cancelling a sum-of-squares term. This adapts the Kondratiev-Kuna-Ohlerich argument from continuum spatial birth-and-death dynamics to the discrete Glauber setting on graphs.

Significance. If the central algebraic cancellation holds, the paper supplies a streamlined alternative to the Chen-Chen-Chen-Yin-Zhang breakthrough, highlighting the portability of Bakry-Émery techniques to discrete spin systems without local-to-global machinery. The self-contained character and absence of fitted parameters are positive features.

major comments (1)
  1. [the proof of the Poincaré inequality (main argument following the abstract)] The key step is the expansion of the Dirichlet form for the discrete Glauber generator (sum over vertex updates whose rates depend on the hard-core configuration and the random regular graph). The manuscript must explicitly compute the resulting cross terms between distinct vertices and neighborhoods and confirm they cancel identically or are absorbed without new assumptions; failure of exact cancellation would invalidate the Poincaré inequality beyond uniqueness. This algebraic verification is load-bearing for the claim that the adaptation introduces no new technical obstacles.
minor comments (1)
  1. Clarify the precise range of degrees and fugacity parameters for which the result holds, and ensure the statement of the Poincaré inequality matches the mixing-time conclusion.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and for highlighting the importance of the algebraic verification in the proof. We address the single major comment below.

read point-by-point responses

  1. Referee: The key step is the expansion of the Dirichlet form for the discrete Glauber generator (sum over vertex updates whose rates depend on the hard-core configuration and the random regular graph). The manuscript must explicitly compute the resulting cross terms between distinct vertices and neighborhoods and confirm they cancel identically or are absorbed without new assumptions; failure of exact cancellation would invalidate the Poincaré inequality beyond uniqueness. This algebraic verification is load-bearing for the claim that the adaptation introduces no new technical obstacles.

    Authors: The manuscript already carries out this explicit computation in the main argument (immediately after the statement of the Poincaré inequality). The Dirichlet form is expanded as an L²-norm involving the generator; the cross terms between distinct vertices and their neighborhoods are then computed directly using the regularity of the graph and the locality of Glauber updates. These cross terms cancel identically, leaving a non-negative sum-of-squares expression whose positivity holds exactly beyond the tree uniqueness threshold. The cancellation uses only the random-regular structure and the hard-core constraints, with no additional assumptions or parameters. This mirrors the Kondratiev–Kuna–Ohlerich cancellation but is fully discrete. We are happy to add a short clarifying remark or expanded display of the cross-term calculation in a revision if the current presentation is judged insufficiently explicit. revision: partial

Circularity Check

0 steps flagged

No circularity: self-contained algebraic adaptation of external continuum argument

full rationale

The paper derives the Poincaré inequality directly by expanding the Dirichlet form as the L²-norm of the generator and cancelling a sum-of-squares term, adapting the Kondratiev–Kuna–Ohlerich continuum argument to discrete Glauber dynamics on random regular graphs. This is an algebraic manipulation whose validity is independent of any fitted parameters, self-referential definitions, or load-bearing self-citations. The cited prior works (Chen et al. for the breakthrough result and Kondratiev et al. for the continuum technique) have non-overlapping authors and are invoked only for context, not to justify uniqueness or force the choice of coordinates. No step reduces the claimed result to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no information on free parameters, axioms, or invented entities; insufficient detail to populate the ledger.

pith-pipeline@v0.9.1-grok · 5687 in / 1090 out tokens · 32392 ms · 2026-06-29T00:42:54.726679+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

14 extracted references

  1. [1]

    Anari, K

    N. Anari, K. Liu, and S. O. Gharan. Spectral independence in high-dimensional expanders and applications to the hardcore model.SIAM Journal on Computing, 53(6):FOCS20–1, 2021

    2021

  2. [2]

    Bakry and M

    D. Bakry and M. ´Emery. Diffusions hypercontractives. InS´ eminaire de Probabilit´ es XIX 1983/84: Proceedings, pages 177–206. Springer, 2006

    1983

  3. [3]

    Bhatnagar, A

    N. Bhatnagar, A. Sly, and P. Tetali. Decay of correlations for the hardcore model on the d-regular random graph.Electron. J. Probab, 21(9):1–42, 2016

    2016

  4. [4]

    Boudou, P

    A.-S. Boudou, P. Caputo, P. Dai Pra, and G. Posta. Spectral gap estimates for interacting particle systems via a Bochner- type identity.Journal of Functional Analysis, 232(1):222–258, 2006

    2006

  5. [5]

    G. R. Brightwell and P. Winkler. A second threshold for the hard-core model on a Bethe lattice.Random Structures & Algorithms, 24(3):303–314, 2004

    2004

  6. [6]

    X. Chen, Z. Chen, Z. Chen, Y. Yin, and X. Zhang. Rapid mixing on random regular graphs beyond uniqueness. In2025 IEEE 66th Annual Symposium on Foundations of Computer Science—FOCS 2025, pages 2170–2193. IEEE Comput. Soc. Press, Los Alamitos, CA, 2025

    2025

  7. [7]

    X. Chen, Z. Chen, Y. Yin, and X. Zhang. Rapid mixing at the uniqueness threshold. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 879–890, 2025

    2025

  8. [8]

    Z. Chen, K. Liu, and E. Vigoda. Optimal mixing of Glauber dynamics: Entropy factorization via high-dimensional expan- sion. InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1537–1550, 2021

    2021

  9. [9]

    Z. Chen, K. Liu, and E. Vigoda. Rapid mixing of Glauber dynamics up to uniqueness via contraction.SIAM Journal on Computing, 52(1):196–237, 2023

    2023

  10. [10]

    Friedman

    J. Friedman. A proof of Alon’s second eigenvalue conjecture and related problems.Memoirs of the American Mathematical Society, 195(910):0–0, 2008

    2008

  11. [11]

    Kondratiev, T

    Y. Kondratiev, T. Kuna, and N. Ohlerich. Spectral gap for Glauber type dynamics for a special class of potentials.Electronic Journal Of Probability, 18, 2013

    2013

  12. [12]

    Mossel, D

    E. Mossel, D. Weitz, and N. Wormald. On the hardness of sampling independent sets beyond the tree threshold.Probability Theory and Related Fields, 143(3):401–439, 2009

    2009

  13. [13]

    A. Sly. Computational transition at the uniqueness threshold. In2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS), pages 287–296. IEEE, 2010

    2010

  14. [14]

    D. Weitz. Counting independent sets up to the tree threshold. InProceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 140–149. ACM, 2006. Hasso Plattner Institute, University of Potsdam, Germany Email address:andreas.goebel@hpi.de King’s College London, Department of Mathematics Email address:matthew.jenssen@kcl.ac.uk Northwest...

    2006