Expanders

Existence vs. construction

• Of course, many probabilistic method constructions yield constructive algorithms
• Other times, are only existential proofs, or very bad algorithms
• But motivate search for good algorithm

Definition: $(n,d,\alpha,c)$ OR-concentrator

• bipartite $2n$ vertices
• degree at most $d$ in $L$
• expansion $c$ on sets $< \alpha n$.

Applications:

• switching/routing
• ECCs

claim: $(n,18,1/3,2)$-concentrator

• Construct by sampling $d$ random neighbors with replacement
  • $E_s$: Specific size $s$ set has $< cs$ neighbors.
  • fix $S$ of size $s$. $T$ of size $< cs$.
  • prob. $S$ goes to $T$ at most $(cs/n)^{ds}$
  • $\binom{n}{cs}$ sets $T$
  • $\binom{n}{s}$ sets $S$
  • $$ \begin{eqnarray*} \Pr[] &\le &\binom{n}{s}\binom{n}{cs}(cs/n)^{ds}\\ &\le &(en/s)^s(en/cs)^{cs}(cs/n)^{ds}\\ &= &[(s/n)^{d-c-1}e^{c+1}c^{d-c}]^s\\ &\le &[(1/3)^{d-c-1}e^{c+1}c^{d-c}]^s\\ &\le &[(c/3)^d(3e)^{c+1}]^s \end{eqnarray*} $$
  • Take $c=2, d=18$, get $[(2/3)^{18}(3e)^3]^{-s} < 2^{-s}$
  • sum over $s$, get $< 1$

Existence proof

• No known construction this good.
• $NP$-hard to verify
• but some constructions almost this good
• recent progress via zig-zag product