On Counting Independent Sets in Regular Hypergraphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.17468
curl -X POST /api/v1/records/arxiv/2609.17468/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.17468/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'