Math Conjectures

Small-Set Expansion Hypothesis

OPENLandmarkConjectureProposed 2010 · Standard version

Canonical statement

For a finite DD-regular graph G=(V,E)G=(V,E) and a nonempty set S⊆VS\subseteq V, define its edge expansion by
ΦG(S)=∣E(S,V∖S)∣D∣S∣, \Phi_G(S)=\frac{|E(S,V\setminus S)|}{D|S|},
where E(S,V∖S)E(S,V\setminus S) is the set of edges with one endpoint in SS and the other outside SS. For every constant η∈(0,1/2)\eta\in(0,1/2), there is a rational constant δ∈(0,1/2)\delta\in(0,1/2) such that the following promise problem is NPNP-hard, on input sizes for which δ∣V∣\delta|V| is an integer:
YES:some S⊆V with ∣S∣=δ∣V∣ has ΦG(S)≤η;NO:every S⊆V with ∣S∣=δ∣V∣ has ΦG(S)≥1−η. \begin{array}{ll} \text{YES:}&\text{some }S\subseteq V\text{ with }|S|=\delta|V| \text{ has }\Phi_G(S)\leq\eta;\\ \text{NO:}&\text{every }S\subseteq V\text{ with }|S|=\delta|V| \text{ has }\Phi_G(S)\geq1-\eta. \end{array}
View source LaTeX
For a finite \(D\)-regular graph \(G=(V,E)\) and a
nonempty set \(S\subseteq V\), define its edge expansion by
\[
  \Phi_G(S)=\frac{|E(S,V\setminus S)|}{D|S|},
\]
where \(E(S,V\setminus S)\) is the set of edges with one endpoint in
\(S\) and the other outside \(S\). For every constant
\(\eta\in(0,1/2)\), there is a rational constant
\(\delta\in(0,1/2)\) such that the following promise problem is
\(NP\)-hard, on input sizes for which \(\delta|V|\) is an integer:
\[
  \begin{array}{ll}
  \text{YES:}&\text{some }S\subseteq V\text{ with }|S|=\delta|V|
  \text{ has }\Phi_G(S)\leq\eta;\\
  \text{NO:}&\text{every }S\subseteq V\text{ with }|S|=\delta|V|
  \text{ has }\Phi_G(S)\geq1-\eta.
  \end{array}
\]
TCS-028:[RaghavendraSteurer2010SSE][RaghavendraSteurerTulsiani2012SSE][AroraBarakSteurer2015SSE]
Theoretical computer scienceGraph theory

Notes

The hypothesis implies the Unique Games Conjecture and is equivalent to a restricted expansion form of it. Subexponential algorithms and hardness consequences are known, but the stated polynomial-time hardness gap has neither been proved nor algorithmically refuted.
Equivalent standard formulations permit a constant-factor size slack in the NO case; this record fixes the exact-size version.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.