Counting independent sets in expanding bipartite regular graphs
Maurício Collares, Joshua Erde, Anna Geisler, Mihyun Kang · 2025
Read Counting independent sets in expanding bipartite regular graphs by Maurício Collares, Joshua Erde, Anna Geisler, Mihyun Kang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-22255.txt.
Description
Maurício Collares and three co-authors find a precise formula for counting independent sets in a wide family of networks, in this 2025 paper. An independent set is a selection of vertices no two of which are linked by an edge. Counting them exactly is easy only for special graphs; for large ones, even good approximations are prized.
The graphs here are regular, bipartite, and expanding, meaning every vertex has the same number of neighbors, the vertices split into two camps, and the network spreads out robustly. Using a polymer model borrowed from physics and a cluster expansion, the authors write the count as an asymptotic series, sharpening earlier results on famous examples like the hypercube. Their formula also describes what a typical independent set looks like. They prove the family includes all grid-like products of small bipartite regular graphs, a result of interest in its own right.
Catalog record
| CREATOR | Maurício Collares, Joshua Erde, Anna Geisler, Mihyun Kang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 113 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-22255