Relationship between poor spectral expansion and poorly connected subset.

Question

Suppose I have a $d$-regular graph $G = (V, E)$ on $n$ vertices, with second largest eigenvalue $\lambda_2 = cd$, for some $c \in (1/2, 1)$ (which means its spectral expansion is a small constant). Does there exist a subset $S \subset V$ such that $|S| = \theta(n)$ and $E(S, \overline{S}) = \theta(d^2)$?

Answer 1

In general, $\min_{S \subset V(G)} |E(S,\bar{S})|$ $=\Omega(cd\times \min\{|S|,|\bar{S}|\})$.

If $1-c \in \Omega(1)$ then for every subset $S$ such that both $|S|$ and $|\bar{S}|= n-|S|$ are $\theta(n)$, the inequality $|E(S,\bar{S})| = \Omega(cdn) =\Omega(dn)$ holds. So to answer your question, no unless $d=\theta(n)$ too.

[If $|S|$ is so close to $n$ that $n-|S| \approx d$ then of course $|E(S,\bar{S})|$ is only $\theta(d^2)$.]

So for the graph to have such a small cut where there are a large number of vertices on either side, $\lambda_2$ has to be something like $d-\frac{d}{n}$.