# Unique-neighbor expander

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$$

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|.$$
• 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$. May 27 '20 at 19:11
• You wrote "left degree $D$". I don't see how this can be interpreted as an upper bound. May 27 '20 at 19:12