Counting independent sets in regular hypergraphs

József Balogh, Béla Bollobás, Bhargav Narayanan

Research output: Contribution to journalArticlepeer-review

Abstract

Amongst d-regular r-uniform hypergraphs on n vertices, which ones have the largest number of independent sets? While the analogous problem for graphs (originally raised by Granville) is now well-understood, it is not even clear what the correct general conjecture ought to be; our goal here is to propose such a generalisation. Lending credence to our conjecture, we verify it within the class of ‘quasi-bipartite’ hypergraphs (a generalisation of bipartite graphs that seems natural in this context) by adopting the entropic approach of Kahn.

Original languageEnglish (US)
Article number105405
JournalJournal of Combinatorial Theory. Series A
Volume180
DOIs
StatePublished - May 2021

Keywords

  • Entropy
  • Hypergraphs
  • Independent sets

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Counting independent sets in regular hypergraphs'. Together they form a unique fingerprint.

Cite this