What is the tightest upper bound known for the number of independent sets in a graph?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ Upper bound in terms of what parameters of the graph? $\endgroup$– David RicherbyCommented Nov 28, 2014 at 9:44
-
$\begingroup$ @David: I think this question is worthwhile even without specifying the parameters, since there are only two that are typically considered (vertices and vertices/edges); this is reflected in the answers. $\endgroup$– András SalamonCommented Nov 29, 2014 at 13:34
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
The trivial upper bound of $2^n$ (on a graph with $n$ vertices) is as tight as you can get, since a graph that has no edges does indeed have $2^n$ independent sets.
answered Nov 27, 2014 at 12:20
-
6$\begingroup$ Is there such a simple bound that takes into account the number $m$ of edges in the graph? If $I(n,m)$ denotes the maximal number of independent sets in a graph with $n$ vertices and $m$ edges, we have $I(n,0)=2^n$, $I(n,n(n-1)/2)=n+1$ and $I(n,1)=3\cdot 2^{n-2}$ (if I made no mistake). Do we have a closed form formula for $I(n,m)$? $\endgroup$– BrunoCommented Nov 27, 2014 at 16:16
$\begingroup$
$\endgroup$
If $I(n,m)$ denotes the maximal number of independent sets in a graph with $n$ vertices and $m$ edges.
$I(n,n-1) = 2^{n-1}+1$ is achieved by a star (should be easy to prove, start by proving that any graph with a matching of size $3$ has at most $3^3\times 2^{n-6}$ independent sets, then show that we can not have two node disjoint paths of length $3$ and no induced path of length $4$, the only remaining graph will be the star).
Let $k(n,m)$ be minimum number such that $k(k-1)/2 + k(n-k) > m$. Then there exit graphs with $n$ nodes and $m$ edges having $2^{n-k}+k$ independent sets. Namely an independent set of size n-k and k universal vertices. I think this is close to optimal, hence:
$$I(n,m) \ge 2^{n-k(n,m)}+k(n,m)$$
A more precise bound can be derived from David R. Wood's study of number of cliques,On the Maximum Number of Cliques in a Graph