# Are there two-sided $\varepsilon$-expanders with independent sets of size $(1-\varepsilon)n$?

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.