pith. sign in

arxiv: 2604.21847 · v1 · submitted 2026-04-23 · 💻 cs.DS · cs.CC

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold

Nicholas Kocurek , Shayan Oveis Gharan , Dante Tjowasi This is my paper

Pith reviewed 2026-05-09 20:00 UTC · model grok-4.3

classification 💻 cs.DS cs.CC
keywords hardcore modelsampling algorithmsrandom regular bipartite graphsMarkov chain Monte Carlospectral expanderstrickle-down theorempartition functionfugacity
0
0 comments X

The pith

An efficient sampling algorithm generates independent sets from the hardcore model on random regular bipartite graphs for fugacity up to roughly 1 over square root of the degree.

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

The paper establishes an efficient algorithm for sampling from the hardcore model on random regular bipartite graphs when the fugacity parameter λ is at most about 1 over square root of the graph degree. It introduces two new Markov chains that handle complementary regimes of the parameter space and proves their rapid mixing by showing that associated simplicial complexes are top-link spectral expanders, then applying the trickle-down theorem. A reader would care because this extends the range of efficient sampling beyond the uniqueness threshold and, when combined with earlier results, yields a fully polynomial randomized approximation scheme for the partition function at every fugacity value. The approach relies on high-dimensional expansion to control the dynamics of the chains.

Core claim

We design an efficient sampling algorithm to generate samples from the hardcore model on random regular bipartite graphs as long as λ ≲ 1/√Δ, where Δ is the degree. Combined with recent work of Jenssen, Keevash and Perkins this implies an FPRAS for the partition function of the hardcore model on random regular bipartite graphs at any fugacity. Our algorithm is shown by analyzing two new Markov chains that work in complementary regimes. Our proof then proceeds by showing the corresponding simplicial complexes are top-link spectral expanders and appealing to the trickle-down theorem to prove fast mixing.

What carries the argument

Two complementary Markov chains whose state spaces are simplicial complexes shown to be top-link spectral expanders, with fast mixing proved via the trickle-down theorem.

If this is right

  • Samples from the hardcore model can be generated in polynomial time for all λ ≲ 1/√Δ on random regular bipartite graphs.
  • An FPRAS for the partition function holds for the hardcore model on these graphs at every fugacity value.
  • The two Markov chains mix rapidly in their respective regimes because of the top-link expansion property.
  • The uniqueness threshold can be surpassed for sampling purposes on this family of graphs.

Where Pith is reading between the lines

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

  • The same expansion-based technique may extend to sampling other spin systems on bipartite graphs with similar degree regularity.
  • Top-link spectral expansion could serve as a general criterion for designing fast-mixing chains in high-dimensional settings beyond the hardcore model.
  • If the expansion property holds for a wider range of λ, the sampling threshold could be pushed closer to the computational limit.
  • The method suggests that proving expansion in top links might simplify analysis for other Markov chains used in approximate counting.

Load-bearing premise

The simplicial complexes for the two Markov chains are top-link spectral expanders.

What would settle it

A direct computation showing that the mixing time of either Markov chain becomes super-polynomial on a random regular bipartite graph for some λ slightly larger than 1/√Δ would disprove the efficiency of the sampler.

read the original abstract

We design an efficient sampling algorithm to generate samples from the hardcore model on random regular bipartite graphs as long as $\lambda \lesssim \frac{1}{\sqrt{\Delta}}$, where $\Delta$ is the degree. Combined with recent work of Jenssen, Keevash and Perkins this implies an FPRAS for the partition function of the hardcore model on random regular bipartite graphs at any fugacity. Our algorithm is shown by analyzing two new Markov chains that work in complementary regimes. Our proof then proceeds by showing the corresponding simplicial complexes are top-link spectral expanders and appealing to the trickle-down theorem to prove fast mixing.

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

Summary. The paper designs an efficient sampling algorithm for the hardcore model on random regular bipartite graphs for λ ≲ 1/√Δ. It constructs two new Markov chains operating in complementary regimes, proves fast mixing by showing that the associated simplicial complexes are top-link spectral expanders, and invokes the trickle-down theorem. Combined with the work of Jenssen, Keevash and Perkins, this yields an FPRAS for the partition function at any fugacity.

Significance. If the central claims hold, the result completes the picture for approximate sampling and counting in the hardcore model on random regular bipartite graphs by covering the regime up to the uniqueness threshold, where prior techniques were insufficient. The technical approach of establishing top-link expansion to apply the trickle-down theorem is a notable contribution that strengthens the connection between high-dimensional expanders and MCMC analysis for statistical physics models.

major comments (1)
  1. [Abstract and the section establishing top-link spectral expansion] The proof that the simplicial complexes are top-link spectral expanders (as stated in the abstract and developed in the main analysis) is the single load-bearing step for the fast-mixing claims. Explicit bounds must be given showing that the second eigenvalue of every top link satisfies the gap condition required by the trickle-down theorem (typically a gap of 1 − O(1/k) in dimension k) with high probability over the random regular bipartite graph, uniformly up to λ ≲ 1/√Δ. If the expansion constant degrades exactly at this threshold or fails to be uniform, the mixing-time guarantees for both chains collapse.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for highlighting the importance of the top-link spectral expansion argument. We agree that this is the central technical step and appreciate the opportunity to strengthen the presentation of the eigenvalue bounds.

read point-by-point responses

  1. Referee: [Abstract and the section establishing top-link spectral expansion] The proof that the simplicial complexes are top-link spectral expanders (as stated in the abstract and developed in the main analysis) is the single load-bearing step for the fast-mixing claims. Explicit bounds must be given showing that the second eigenvalue of every top link satisfies the gap condition required by the trickle-down theorem (typically a gap of 1 − O(1/k) in dimension k) with high probability over the random regular bipartite graph, uniformly up to λ ≲ 1/√Δ. If the expansion constant degrades exactly at this threshold or fails to be uniform, the mixing-time guarantees for both chains collapse.

    Authors: We agree that explicit, uniform bounds on the second eigenvalue are necessary to rigorously invoke the trickle-down theorem. Our current analysis already shows that the relevant simplicial complexes are top-link spectral expanders with high probability for λ ≲ 1/√Δ, but the eigenvalue gap is stated in asymptotic form. In the revised manuscript we will add an explicit derivation (in a new subsection of the main analysis and a supporting appendix) establishing that every top link has second eigenvalue at most 1 − Ω(1/k) with high probability, uniformly over the stated range of λ. The argument uses the random regular bipartite structure and a direct spectral calculation that remains valid up to the uniqueness threshold; we will also include a short paragraph confirming that the gap does not degrade at the boundary of the regime. This change will make the application of the trickle-down theorem fully explicit for both Markov chains without altering any claims. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation relies on direct spectral analysis and external trickle-down theorem

full rationale

The paper constructs two new Markov chains for the hardcore model on random regular bipartite graphs and establishes fast mixing by proving that the associated simplicial complexes are top-link spectral expanders (with the second eigenvalue bounded below the trickle-down threshold with high probability), then invoking the trickle-down theorem. This expansion bound is derived directly from the random regular bipartite graph model rather than being defined in terms of the target mixing time or partition function. The overall FPRAS claim combines the new regime with an independent external result of Jenssen, Keevash and Perkins; no self-definitional equations, fitted inputs renamed as predictions, or load-bearing self-citations are present. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the applicability of the trickle-down theorem to top-link spectral expanders of simplicial complexes arising from the hardcore model and on expansion properties holding for random regular bipartite graphs.

axioms (2)
  • standard math The trickle-down theorem applies once top links of the simplicial complexes are shown to be spectral expanders.
    Invoked to deduce fast mixing of the Markov chains from local expansion properties.
  • domain assumption Random regular bipartite graphs induce simplicial complexes whose top links satisfy the required spectral expansion.
    Assumed to hold for the random model in the stated regime.

pith-pipeline@v0.9.0 · 5408 in / 1406 out tokens · 87491 ms · 2026-05-09T20:00:13.281881+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

20 extracted references · 20 canonical work pages

  1. [1]

    Entropic independence: optimal mixing of down-up random walks

    [AJK+22] Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong. Entropic independence: optimal mixing of down-up random walks. InSTOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1418–1430. ACM,

    work page 2022

  2. [2]

    Trickle-Down in Localization Schemes and Applications

    [AKV24] Nima Anari, Frederic Koehler, and Thuy-Duong Vuong. Trickle-Down in Localization Schemes and Applications. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1094–1105. ACM,

    work page 2024

  3. [3]

    Improved analysis of higher order random walks and applications

    24 [AL20] Vedat Levi Alev and Lap Chi Lau. Improved analysis of higher order random walks and applications. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1198–1211. ACM,

    work page 2020

  4. [4]

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

    [ALG20] Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. Spectral Independence in High- Dimensional Expanders and Applications to the Hardcore Model. In61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1319–1330. IEEE,

    work page 2020

  5. [5]

    On mixing of markov chains: Coupling, spectral independence, and entropy factorization

    [BCC+22] Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Stefankovic, and Eric Vigoda. On mixing of markov chains: Coupling, spectral independence, and entropy factorization. InProceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 3670–3692. SIAM,

    work page 2022

  6. [6]

    Rapid mixing on random regular graphs beyond uniqueness

    [CCC+25] Xiaoyu Chen, Zejia Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang. Rapid Mixing on Random Regular Graphs beyond Uniqueness.CoRR, abs/2504.03406,

    work page arXiv

  7. [7]

    Rapid Mixing at the Uniqueness Threshold

    [CCYZ25] Xiaoyu Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang. Rapid Mixing at the Uniqueness Threshold. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 879–890. ACM,

    work page 2025

  8. [8]

    Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains (extended abstract)

    [CE22] Yuansi Chen and Ronen Eldan. Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains (extended abstract). In63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 110–122. IEEE,

    work page 2022

  9. [9]

    Rapid mixing of Glauber dynamics via spectral independence for all degrees

    [CFYZ21] Xiaoyu Chen, Weiming Feng, Yitong Yin, and Xinyuan Zhang. Rapid mixing of Glauber dynamics via spectral independence for all degrees. In62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 137–148. IEEE,

    work page 2021

  10. [10]

    Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction

    [CLV20] Zongchen Chen, Kuikui Liu, and Eric Vigoda. Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction. In61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1307–1318. IEEE,

    work page 2020

  11. [11]

    Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion

    [CLV21] Zongchen Chen, Kuikui Liu, and Eric Vigoda. Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion. InSTOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1537–1550. ACM,

    work page 2021

  12. [12]

    Dyer, Alan M

    [DFJ99] Martin E. Dyer, Alan M. Frieze, and Mark Jerrum. On Counting Independent Sets in Sparse Graphs. In40th Annual Symposium on Foundations of Computer Science, 25 FOCS 1999, New York, NY, USA, October 17-18, 1999, pages 210–217. IEEE Computer Society,

    work page 1999

  13. [13]

    Dyer, Leslie Ann Goldberg, Catherine S

    [DGGJ00] Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, and Mark Jerrum. On the relative complexity of approximate counting problems. InApproximation Algo- rithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Saarbr¨ ucken, Germany, September 5-8, 2000, Proceedings, volume 1913 ofLecture Notes in Computer Science...

    work page 2000

  14. [14]

    High Dimensional Expanders Imply Agreement Ex- panders

    [DK17] Irit Dinur and Tali Kaufman. High Dimensional Expanders Imply Agreement Ex- panders. In58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 974–985. IEEE Computer Soci- ety,

    work page 2017

  15. [15]

    Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs

    [DP21] Ewan Davies and Will Perkins. Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs. In48th International Colloquium on Automata, Lan- guages, and Programming, ICALP 2021, Glasgow, Scotland (Virtual Conference), July 12-16, 2021, volume 198 ofLIPIcs, pages 62:1–62:18. Schloss Dagstuhl - Leibniz- Zentrum f¨ ur Informatik,

    work page 2021

  16. [16]

    A proof of Alon’s second eigenvalue conjecture

    [Fri03] Joel Friedman. A proof of Alon’s second eigenvalue conjecture. InProceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 720–724. ACM,

    work page 2003

  17. [17]

    Optimal mixing of the down-up walk on independent sets of a given size

    [JMPV23] Vishesh Jain, Marcus Michelen, Huy Tuan Pham, and Thuy-Duong Vuong. Optimal mixing of the down-up walk on independent sets of a given size. In64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 1665–1681. IEEE,

    work page 2023

  18. [18]

    On the Power of Unique 2-Prover 1-Round Games

    [Kho02] Subhash Khot. On the Power of Unique 2-Prover 1-Round Games. InProceedings of the 17th Annual IEEE Conference on Computational Complexity, Montr´ eal, Qu´ ebec, Canada, May 21-24, 2002, page

    work page 2002

  19. [19]

    Computational Transition at the Uniqueness Threshold

    [Sly10] Allan Sly. Computational Transition at the Uniqueness Threshold. In51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, Las Vegas, Nevada, USA, October 23-26, 2010, pages 287–296. IEEE Computer Society,

    work page 2010

  20. [20]

    The Computational Hardness of Counting in Two-Spin Models on d-Regular Graphs

    [SS12] Allan Sly and Nike Sun. The Computational Hardness of Counting in Two-Spin Models on d-Regular Graphs. In53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 361–369. IEEE Computer Society,

    work page 2012