Asymptotically Enumerating Independent Sets in Regular $k$-Partite $k$-Uniform Hypergraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915071270060032 |
|---|---|
| author | Arras, Patrick Garbe, Frederik Joos, Felix |
| author_facet | Arras, Patrick Garbe, Frederik Joos, Felix |
| contents | The number of independent sets in regular bipartite expander graphs can be efficiently approximated by expressing it as the partition function of a suitable polymer model and truncating its cluster expansion. While this approach has been extensively used for graphs, surprisingly little is known about analogous questions in the context of hypergraphs. In this work, we apply this method to asymptotically determine the number of independent sets in regular $k$-partite $k$-uniform hypergraphs which satisfy natural expansion properties. The resulting formula depends only on the local structure of the hypergraph, making it computationally efficient. In particular, we provide a simple closed-form expression for linear hypergraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_14845 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Asymptotically Enumerating Independent Sets in Regular $k$-Partite $k$-Uniform Hypergraphs Arras, Patrick Garbe, Frederik Joos, Felix Combinatorics Discrete Mathematics The number of independent sets in regular bipartite expander graphs can be efficiently approximated by expressing it as the partition function of a suitable polymer model and truncating its cluster expansion. While this approach has been extensively used for graphs, surprisingly little is known about analogous questions in the context of hypergraphs. In this work, we apply this method to asymptotically determine the number of independent sets in regular $k$-partite $k$-uniform hypergraphs which satisfy natural expansion properties. The resulting formula depends only on the local structure of the hypergraph, making it computationally efficient. In particular, we provide a simple closed-form expression for linear hypergraphs. |
| title | Asymptotically Enumerating Independent Sets in Regular $k$-Partite $k$-Uniform Hypergraphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2412.14845 |