1
$\begingroup$

I want to solve Problem 4.10 from Randomness by Salil Vadhan. https://people.seas.harvard.edu/~salil/cs225/spring15/PS3.pdf

Consider a bipartite expander $G$ with left degree $D$ so that every subset $S$ of the left vertices with at most $K$ vertices has at least $(1-\epsilon)D|S|$ neighbors. Then $G$ also has the property that it has $(1-2\epsilon)D|S|$ unique neighbors. Unique meaning that it has exactly one corresponding vertex from $S$.

I recognize that the new expansion factor is $(1-2\epsilon)D = 2\cdot(1-\epsilon)D -D$

$\endgroup$
1
$\begingroup$

Let $S$ be a subset of at most $K$ vertices. Let $a_d$ be the number of vertices on the right side which are connected to exactly $d$ vertices in $S$. Since the left degree is $D$, $$ \sum_{d \geq 1} da_d = D|S|. $$ Since $S$ has at least $(1-\epsilon)D|S|$ neighbors, $$ \sum_{d \geq 1} a_d \geq (1-\epsilon)D|S|. $$ Therefore $$ \sum_{d \geq 2} a_d \leq \sum_{d \geq 1} (d-1) a_d = \sum_{d \geq 1} da_d - \sum_{d \geq 1} a_d \leq D|S| - (1-\epsilon)D|S| = \epsilon D|S|. $$ It follows that $$ a_1 = \sum_{d \geq 1} a_d - \sum_{d \geq 2} a_d \geq (1-\epsilon)D|S| - \epsilon D|S| = (1-2\epsilon)D|S|. $$

$\endgroup$
4
  • $\begingroup$ Thank you! Didn't think of this counting. However, as I understood it $D$ is the upper bound so the first equation should be $\leq$. $\endgroup$
    – Mark Regev
    May 27 '20 at 19:11
  • $\begingroup$ You wrote "left degree $D$". I don't see how this can be interpreted as an upper bound. $\endgroup$ May 27 '20 at 19:12
  • $\begingroup$ The vasy majority of the time, we do assume that expanders are regular. $\endgroup$ May 27 '20 at 19:12
  • $\begingroup$ Sorry, I must have used another definition. $\endgroup$
    – Mark Regev
    May 27 '20 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.