Asymptotically Enumerating Independent Sets in Regular k k -Partite k k -Uniform Hypergraphs

Patrick Arras, Frederik Garbe, and Felix Joos · 2024

Read Asymptotically Enumerating Independent Sets in Regular k k -Partite k k -Uniform Hypergraphs by Patrick Arras, Frederik Garbe, and Felix Joos (2024) 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-2412-14845.txt.

Description

Patrick Arras, Frederik Garbe, and Felix Joos count independent sets in a family of hypergraphs, networks where each edge joins several vertices at once. An independent set picks vertices so no edge sits fully inside the pick. Counting such sets in regular bipartite graphs is a solved art; hypergraphs lagged behind.

The method borrows from physics: treat the count as a polymer model's partition function and trim its cluster expansion. For regular, well-spread hypergraphs split into equal parts, the count settles into a formula based only on local structure. That makes it fast to compute. For linear hypergraphs, where edges barely overlap, the authors give a simple closed form.

Catalog record

CREATORPatrick Arras, Frederik Garbe, and Felix Joos
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-14845

Browse the full library · About the Tower of Babel