Given a graph $G=(V,E)$ and a $\delta > 0$ one wants to calculate $h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S)$. ($\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - \vert S\vert \} }$) The ``small-set expansion conjecture" states that it is NP-Hard to determine if this is below $\epsilon$ or above $1-\epsilon$ for $\epsilon = 1/O(log(\frac{1}{\delta} ) )$
For context one notes that $h(G,\delta = \frac{1}{2})$ is the Cheeger constant which is known to be NP-hard to bound. But there does seem to exist values of $\delta$ (which ones?) for which $\phi(G,\delta)$ can be computed in polynomial time?
Towards understanding the small-set expansion conjecture one seems to prove this statement,
- If $W$ is the span of the Laplacian eigenvectors of $G$ such that their eigenvalues are less than some $\lambda \in [0,1]$ and if every $w \in W$ satisfies $\mathbb{E}_i[w_i^4 ] \leq C ( E_i [w_i ^2 ] )^2$ then for every set $S$ of measure $\delta$ we have $\phi(S) \geq \lambda(1 - \sqrt{C \delta} )$
My questions are,
Its not clear from the proof of this above theorem as to what exactly is the meaning of ``set $S$ of measure $\delta$". Does it mean that $\vert S \vert \leq \delta \vert V\vert$ as required in the conjecture statement?
How does the above theorem help understand the conjecture stated at the beginning? What is the relationship between the two?
Why should such vectors $w$ exists as demanded in the theorem? What is the intuition behind looking at such $w$?
What is the intuition behind choosing that specific value of $\epsilon$ as in the statement of the conjecture?
