The number of independent sets in an irregular graph

DOI10.1016/j.jctb.2019.01.007zbMath1415.05082arXiv1805.04021OpenAlexW3102510373WikidataQ128371942 ScholiaQ128371942MaRDI QIDQ2312617

Yufei Zhao, Mehtaab Sawhney, David Stoner, Ashwin Sah

Publication date: 17 July 2019

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

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

zbMATH Keywords

independent setKahn's conjecture

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

Interview with Yufei Zhao ⋮ On the maximum number of maximum dissociation sets in trees with given dissociation number ⋮ Independent sets in the middle two layers of Boolean lattice ⋮ A proof of the upper matching conjecture for large graphs ⋮ A reverse Sidorenko inequality

Cites Work

• Unnamed Item
• Hypergraph containers
• The Widom-Rowlinson model, the hard-core model and the extremality of the complete graph
• The number of independent sets in a graph with small maximum degree
• A reverse Sidorenko inequality
• Some intersection theorems for ordered sets and graphs
• Independent sets in regular graphs and sum-free subsets of finite groups
• On kissing numbers and spherical codes in high dimensions
• Counting proper colourings in 4-regular graphs via the Potts model
• The maximum number of complete subgraphs in a graph with given maximum degree
• Bounding the partition function of spin-systems
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• The Bipartite Swapping Trick on Graph Homomorphisms
• On replica symmetry of large deviations in random graphs
• The Number of Independent Sets in a Regular Graph
• Hypergraphs, Entropy, and Inequalities
• Extremal Regular Graphs: Independent Sets and Graph Homomorphisms
• On the average size of independent sets in triangle-free graphs
• ON THE HARD SPHERE MODEL AND SPHERE PACKINGS IN HIGH DIMENSIONS
• On weighted graph homomorphisms
• Extremes of the internal energy of the Potts model on cubic graphs
• Independent sets in hypergraphs
• Information Inequalities for Joint Distributions, With Interpretations and Applications
• Independent sets, matchings, and occupancy fractions

This page was built for publication: The number of independent sets in an irregular graph