Counting Independent Sets and Generalized Colorings in Graphs with Various Restrictions

An n-vertex, <i>d</i>-regular graph can have at most 2^<em>n</em>^/2+o^<em>d</em>⁽^<em>n</em>⁾ independent sets. We address this upper bound when we impose the additional condition that the graph has independence number at most α. In particular, we show that for a sequence of d_<em>n</em>-regular <i>n</i>-vertex graphs <i>G</i>_<em>n</em><i> </i>with independence number at most <i>α</i>_<em>n</em>, if dn → ∞ and <i>(α</i>_<em>n</em><i>)/n</i> → <i>c</i>_<em>α</em>where 0 &lt; cα ≤ 1/2, then <i>G</i>_<em>n</em> has at most <i>k(c</i>_<em>α</em><i>)</i>^{<em>n+o(n</em>}^<em>)</em> independent sets, where <i>k(c</i>_<em>α</em><i>)</i> is an explicit constant which we show is as small as possible. We also prove an analogous result when 1/2 &lt; <i>c</i>_<em>α</em> &lt; 1, subject to the additional condition that <i>(d</i>_<em>n)</em><i>/n </i><i>→</i><i> c</i>_<em>d</em>, where 0 &lt; <i>c</i>_<em>d</em> ≤ 1 - <i>c</i>_<em>α</em>. Our proofs use both graph container arguments and constructive techniques. We further refine our results by giving the asymptotic behavior of the maximum number of independent sets of a fixed size scaling with n of an n-vertex d-regular graph with independence number at most <i>α</i>. Finally, we consider some exact results on maximizing the number of graph homomorphisms from an n-vertex graph <i>G</i> with independence number <i>α</i> to certain target graphs. We conclude by considering some open questions about proper <i>q</i>-colorings.