1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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, 2013 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, 2013 at 9:22

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.