Terry Tao's notes on expander graphs has the following exercise:

Exercise 13 Let $G$ be a $k$-regular graph on $n$ vertices that is a two-sided $\epsilon$-expander for some $n > k \geq 1$ and $\epsilon>0$. Show that any independent set in $G$ has cardinality at most $(1-\epsilon) n$.

Is this bound known to be tight?


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.