Skip to content
DraconiticResearch
Search Sources API
190,335 studies31 sourcesUpdated 25 min ago
PreprintCC BY-NC-SA 4.0arXiv

On Counting Independent Sets in Regular Hypergraphs

  • Michail Sarantis
  • Prasad Tetali
  • Zeyu Zheng
Open at sourcePDFDOICite

Abstract

Balogh, Bollobás and Narayanan conjectured that among all finite simple r-uniform d-regular hypergraphs, the number of weak independent sets is maximized by a natural quasi-bipartite construction Hr,d. We give three types of evidence for this conjecture. For every fixed r, we prove the conjectured asymptotic exponential rate whenever the twin quotient has maximum pair codegree o(d). The proof uses the hypergraph container method. For hypergraphs with no cross-edges, the occupancy method gives the sharper error bound Or(log d/d). We show that a stronger version of the conjecture in terms of the so-called occupancy fraction is not true, by providing a counterexample for every r≥ 3. We also prove exact cases of the conjecture when the hypergraph is $2$-regular. Using an entropy decomposition in the dual edge-cover problem, we settle every odd r and the case (r,d)=(4,2).

Related

  1. Counting almost independent sets in regular graphs
    Gaia Carenini
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Random independent sets in uncrowded hypergraphs
    Abhishek Dhawan, Lina Li, Abhishek Methuku +2
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Random independent sets in triangle-free and linear Berge-C4-free hypergraphs
    Jing Yu, Junchi Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. On the growth of weak regular partitions in k-uniform hypergraphs
    H. Sheats, C. Terry
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsLogic & foundationsarXiv
  5. The upper bounds on occupancy fraction and variance fraction for linear regular uniform hypergraphs
    Weiyuan Zhang, Kexiang Xu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{sarantis2026counting,
  title = {{On Counting Independent Sets in Regular Hypergraphs}},
  author = {Michail Sarantis and Prasad Tetali and Zeyu Zheng},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.17468},
  eprint = {2609.17468},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.17468},
  note = {CC BY-NC-SA 4.0},
}
RIS
TY  - UNPB
TI  - On Counting Independent Sets in Regular Hypergraphs
AU  - Michail Sarantis
AU  - Prasad Tetali
AU  - Zeyu Zheng
PY  - 2026
DA  - 2026/09/15
PB  - arXiv
DO  - 10.48550/arxiv.2609.17468
UR  - https://arxiv.org/abs/2609.17468
AB  - Balogh, Bollobás and Narayanan conjectured that among all finite simple r-uniform d-regular hypergraphs, the number of weak independent sets is maximized by a natural quasi-bipartite construction H_r,d. We give three types of evidence for this conjecture. For every fixed r, we prove the conjectured asymptotic exponential rate whenever the twin quotient has maximum pair codegree o(d). The proof uses the hypergraph container method. For hypergraphs with no cross-edges, the occupancy method gives the sharper error bound O_r(log d/d). We show that a stronger version of the conjecture in terms of the so-called occupancy fraction is not true, by providing a counterexample for every r≥ 3. We also prove exact cases of the conjecture when the hypergraph is $2$-regular. Using an entropy decomposition in the dual edge-cover problem, we settle every odd r and the case (r,d)=(4,2).
ER  -