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.

一个n顶点的d正则图（d-regular graph）至多可拥有$2^{n/2 + o_d(n)}$个独立集（independent sets）。当我们额外要求该图的独立数（independence number）不超过α时，我们对该上界问题展开了研究。具体而言，我们证明：对于一列满足独立数至多为$alpha_n$的$d_n$正则n顶点图$G_n$，若$d_n o infty$且$alpha_n / n o c_alpha$，其中$0 < c_alpha leq 1/2$，则$G_n$至多可拥有$k(c_alpha)^{n + o(n)}$个独立集，其中$k(c_alpha)$为一显式常数，且我们证明该常数已达到最小可能值。
当$1/2 < c_alpha < 1$时，我们也证明了类似结论，但此时需额外满足$d_n / n o c_d$，其中$0 < c_d leq 1 - c_alpha$。我们的证明同时结合了图容器方法（graph container arguments）与构造性技巧（constructive techniques）。
我们进一步细化了研究结果，给出了独立数不超过α的n顶点d正则图中，规模固定且随n缩放的独立集的最大数的渐近行为。
我们还得到了若干精确结果：针对独立数为α的n顶点图$G$，最大化其到特定目标图的图同态（graph homomorphisms）数量的问题。
最后，我们就有关正常q着色（proper q-colorings）的若干公开问题展开讨论，作为本文的结尾。