Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911618723479552 |
|---|---|
| author | Kocurek, Nicholas Gharan, Shayan Oveis Tjowasi, Dante |
| author_facet | Kocurek, Nicholas Gharan, Shayan Oveis Tjowasi, Dante |
| contents | We design an efficient sampling algorithm to generate samples from the hardcore model on random regular bipartite graphs as long as $λ\lesssim \frac{1}{\sqrtΔ}$, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_21847 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold Kocurek, Nicholas Gharan, Shayan Oveis Tjowasi, Dante Data Structures and Algorithms Computational Complexity We design an efficient sampling algorithm to generate samples from the hardcore model on random regular bipartite graphs as long as $λ\lesssim \frac{1}{\sqrtΔ}$, 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. |
| title | Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2604.21847 |