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

Autor:	Arras, Patrick, Garbe, Frederik, Joos, Felix
Rok vydání:	2024
Předmět:	Mathematics - Combinatorics Computer Science - Discrete Mathematics
Druh dokumentu:	Working Paper
Popis:	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. Comment: 21 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2412.14845 Zobrazit plný text záznamu View this record from Arxiv