3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ I think cstheory.se would be a better fit for this question. The OP should also reveal their sources – specifically where the statement "one seems to prove" comes from. Meanwhile, let me just comment that a set of measure $\delta$ is what the OP thinks it is. $\endgroup$ Mar 8, 2015 at 23:26
  • $\begingroup$ @YuvalFilmus I am referring to Lemma 8 here, boazbarak.org/sos/files/lec2d.pdf (experience says that its harder to ask questions on cstheory.se than here, there is always a much higher probability of a question being closed down there - so I didn't want to take the risk! - may be I can try again if you insist!) Though it would be great if you can put in your answers here :D $\endgroup$
    – user6818
    Mar 9, 2015 at 17:20
  • 1
    $\begingroup$ @YuvalFilmus I cross-posted there, cstheory.stackexchange.com/questions/30742/… $\endgroup$
    – user6818
    Mar 9, 2015 at 23:27

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.