3
$\begingroup$

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?

$\endgroup$

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.