MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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. – Douglas S. Stones Jun 25 '13 at 21:22
$k \rightarrow \infty$ as $n \rightarrow \infty$. In the case I'm thinking of $k=2^{\Theta(\sqrt{\log{n}}})$. – karpasi Jun 27 '13 at 9:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.