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 language | English (US) |
---|---|
Article number | 105405 |
Journal | Journal of Combinatorial Theory. Series A |
Volume | 180 |
DOIs | |
State | Published - May 2021 |
Keywords
- Entropy
- Hypergraphs
- Independent sets
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics