Counting independent sets in percolated graphs via the Ising model
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914562034368512 |
|---|---|
| author | Geisler, Anna Kang, Mihyun Sarantis, Michail Wdowinski, Ronen |
| author_facet | Geisler, Anna Kang, Mihyun Sarantis, Michail Wdowinski, Ronen |
| contents | Given a graph $G$, we form a random subgraph $G_p$ by including each edge of $G$ independently with probability $p$. We provide an asymptotic expansion of the expected number of independent sets in random subgraphs of regular bipartite graphs satisfying certain vertex-isoperimetric properties, extending the work of Kronenberg and Spinka on the percolated hypercube. Combining graph containers with the cluster expansion from statistical physics, we give an expansion of the partition function of the Ising model in certain range of the parameters. Among other applications, we obtain results for even tori of growing side-length. As a tool, we prove a refined container lemma for the Ising model, which mildly improves recent bounds of Jenssen, Malekshahian, and Park. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_08715 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Counting independent sets in percolated graphs via the Ising model Geisler, Anna Kang, Mihyun Sarantis, Michail Wdowinski, Ronen Combinatorics Given a graph $G$, we form a random subgraph $G_p$ by including each edge of $G$ independently with probability $p$. We provide an asymptotic expansion of the expected number of independent sets in random subgraphs of regular bipartite graphs satisfying certain vertex-isoperimetric properties, extending the work of Kronenberg and Spinka on the percolated hypercube. Combining graph containers with the cluster expansion from statistical physics, we give an expansion of the partition function of the Ising model in certain range of the parameters. Among other applications, we obtain results for even tori of growing side-length. As a tool, we prove a refined container lemma for the Ising model, which mildly improves recent bounds of Jenssen, Malekshahian, and Park. |
| title | Counting independent sets in percolated graphs via the Ising model |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2504.08715 |