Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|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
add comment

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.