Counting independent sets in structured graphs

Counting independent sets in graphs and hypergraphs under a variety of restrictions is a classical question with a long history. It is the subject of the celebrated container method which found numerous spectacular applications over the years. We consider the question of how many independent sets we can have in a graph under structural restrictions. We show that any n-vertex graph with independence number α without bKₐ as an induced subgraph has at most nO(1) · αO(α) independent sets. This substantially improves the trivial upper bound of nα, whenever α ≤ nᵒ⁽¹⁾ and gives a characterization of graphs forbidding of which allows for such an improvement. It is also in general tight up to a constant in the exponent since there exist triangle-free graphs with αΩ(α) independent sets. We also prove that if one in addition assumes the ground graph is chi-bounded one can improve the bound to nO(1) · 2O(α) which is tight up to a constant factor in the exponent.