# Excluding linear size independent sets in graphs

What are some known criteria of excluding large independent sets (linear size) in k-regular graphs?

I know one criterion is that the smallest eigenvalue of the adjacency matrix shouldn't be too small ($|\lambda_n|=o(k)$). Are there any others? or, alternatively, what are the ways of approximating the smallest eigenvalue.

-
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