Counting independent sets in expanding bipartite regular graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913763804839936 |
|---|---|
| author | Collares, Maurício Erde, Joshua Geisler, Anna Kang, Mihyun |
| author_facet | Collares, Maurício Erde, Joshua Geisler, Anna Kang, Mihyun |
| contents | In this paper we provide an asymptotic expansion for the number of independent sets in a general class of regular, bipartite graphs satisfying some vertex-expansion properties, extending results of Jenssen and Perkins on the hypercube and strengthening results of Jenssen, Perkins and Potukuchi. More precisely, we give an expansion of the independence polynomial of such graphs using a polymer model and the cluster expansion. In addition to the number of independent sets, our results yields information on the typical structure of (weighted) independent sets in such graphs. The class of graphs we consider covers well-studied cases like the hypercube or the middle layers graph, and we show further that it includes any Cartesian product of bipartite, regular base graphs of bounded size. To this end, we prove strong bounds on the vertex expansion of bipartite and regular Cartesian product graphs, which might be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_22255 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Counting independent sets in expanding bipartite regular graphs Collares, Maurício Erde, Joshua Geisler, Anna Kang, Mihyun Combinatorics In this paper we provide an asymptotic expansion for the number of independent sets in a general class of regular, bipartite graphs satisfying some vertex-expansion properties, extending results of Jenssen and Perkins on the hypercube and strengthening results of Jenssen, Perkins and Potukuchi. More precisely, we give an expansion of the independence polynomial of such graphs using a polymer model and the cluster expansion. In addition to the number of independent sets, our results yields information on the typical structure of (weighted) independent sets in such graphs. The class of graphs we consider covers well-studied cases like the hypercube or the middle layers graph, and we show further that it includes any Cartesian product of bipartite, regular base graphs of bounded size. To this end, we prove strong bounds on the vertex expansion of bipartite and regular Cartesian product graphs, which might be of independent interest. |
| title | Counting independent sets in expanding bipartite regular graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2503.22255 |