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.
- Independent sets
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics