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?
I had the following ideas, which may have errors. I borrow all notation from Tao's notes:$\newcommand{\eps}{\varepsilon}$
Let $A$ be the adjacency matrix of the graph. Then for an independent set $S$, $1_S$ would satisfy, $A1_S \cdot 1_S = 0$ with $\cdot$ being the inner product. Write $s = |S|$ and $1_S = s/n 1 + 1_S - s/n1$, so that $$A(s/n 1 + 1_S - s/n 1) \cdot (s/n 1 + 1_S - s/n 1) = s^2/n^2 \times kn + Av \cdot v = 0$$ where $v = 1_S - s/n 1$ has mean zero. Then, $|Av \cdot v| = s^2k/n$. But using the fact that $v$ is orthogonal to $1$ (and $G$ is connected as it is an expander), $$|Av\cdot v| \leq k(1-\varepsilon)||v||^2 = k(1 - \eps)(s^2/n^2 \times (n - s) + (1 - n/s)^2 \times s) = k(1 - \eps)s(n-s)/n$$ Combining with the above, $s \leq (1 - \eps)(n - s) \implies s \leq n (1 - \eps)/(2 - \eps) \leq s (1 - \eps)$ as long as $\eps < 1$ (which will be the case as $G$ is a two-sided expander). The bound $s \leq n(1 - \eps)/(2 - \eps)$ perhaps weakens the hope that the stated bound would be tight.
