Counting independent sets in regular hypergraphs

DOI10.1016/J.JCTA.2021.105405MaRDI QIDQ2229168zbMATH OpenOpenAlexFDO

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

Publication date 22 February 2021

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.09995

zbMATH Keywords

entropyhypergraphsindependent sets

Mathematics Subject Classification ID

Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Applications of graph theory (05C90) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

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 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.

Recommendations

• Counting Independent Sets in Hypergraphs
• Counting independent sets in some classes of (almost) regular graphs
• Counting independent sets in graphs of hyperplane arrangements
• Counting independent sets in graphs
• The number of independent sets in a regular graph
• On the number of independent sets in simple hypergraphs
• On independent sets in hypergraphs
• Independent sets in hypergraphs
• Counting independent sets in Riordan graphs
• Counting independent sets in triangle-free graphs

Cites work

• A reverse Sidorenko inequality
• An entropy approach to the hard-core model on bipartite graphs
• Extremal regular graphs: independent sets and graph homomorphisms
• Independent sets in regular graphs and sum-free subsets of finite groups
• Independent sets, matchings, and occupancy fractions
• On the number of independent sets in uniform, regular, linear hypergraphs
• Some intersection theorems for ordered sets and graphs
• The number of independent sets in a regular graph

Cited in

(9)

• On the number of independent sets in simple hypergraphs
• Coloring the normalized Laplacian for oriented hypergraphs
• Counting independent sets in Riordan graphs
• On the number of independent sets in uniform, regular, linear hypergraphs
• Counting independent sets in graphs of hyperplane arrangements
• Approximate counting of regular hypergraphs
• The independent set sequence of regular bipartite graphs
• Extremal regular graphs: independent sets and graph homomorphisms
• Independent sets in the hypercube revisited

This page was built for publication: Counting independent sets in regular hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2229168)