Suppose we have a graph $G=(V,E)$, and we want to upper bound $|I|/|V|$, where $I$ is the largest independent set in $G$. Then there is the Hoffman bound, which is $|I|/|V| \leq -\lambda_{min}/(\lambda_1-\lambda_{min})$, where $\lambda_1$ and $\lambda_{min}$ are the largest and smallest eigenvalues, respectively, of the adjacency matrix of $G$. One of the problems with this bound, is that it is not "stable", in the following sense: if $|V|$ is large, then adding just one new vertex to $G$, and connecting it to other vertices in whichever way we want, would not change much the size of the largest independent set (normalized by the number of vertices).

However, it might be the case that the smallest eigenvalue in the new graph, is much smaller than the smallest eigenvalue of $G$, which was $\lambda_{min}$. So my question is, are there any other known upper bounds for the size of independent sets, which are more stable, in the sense that adding or removing just a few vertices (or edges) from a large graph, does not change the bound significantly?

  • 3
    $\begingroup$ When you say "linear size", what are the asymptotic conditions (e.g. is $k$ fixed and $n \rightarrow \infty$)? A greedy algorithm gives an independent set of size $\geq n/(k+1)$ in an $n$-vertex $k$-regular graph. $\endgroup$ – Douglas S. Stones Jun 25 '13 at 21:22
  • 1
    $\begingroup$ $k \rightarrow \infty$ as $n \rightarrow \infty$. In the case I'm thinking of $k=2^{\Theta(\sqrt{\log{n}}})$. $\endgroup$ – karpasi Jun 27 '13 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.