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

CREATORMaurício Collares, Joshua Erde, Anna Geisler, Mihyun Kang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE113 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-22255

Browse the full library · About the Tower of Babel