Reminder: This post contains 1358 words
· 4 min read
· by Xianbin
Definitions
\(\textbf{Definition}\). We say that a bipartite expander graph \((\ell,r,D,\gamma,\alpha)\) is \(D\)-left-regular bipartite graph \(G=(L \cup R, E)\) if it satisfies:
\(\forall S \subseteq L\)
such that \(\lvert S \rvert \leq \gamma \ell\) and \(\lvert N(S) \vert \geq \alpha \lvert S \rvert\),
where \(\lvert L \rvert = \ell, \lvert R \rvert = r (r\leq \ell)\).
The above expander graph looks like this. For any subset in the left part of the bipartite graph, it has many neighbors. Intuitively speaking, each incident edge “expands” outside. But, does such an expander exist? If it is a complete bipartite graph, apparently, it is. To prove a general case, we need to construct many such expander graphs. A straightforward idea is to randomly sample \(D\) neighbors for each node from the left part \(L\) in a complete bipartite graph.
Now, let us check this idea.
Theorem 1
\(\textbf{Theorem 1}\). For any \(\epsilon > 0, r\leq \ell\), there exists a \((\ell,r,D, \gamma, \alpha)\) bipartite expander graph where \(\gamma > 0, D\ge 1\) and \(\alpha = (1-\epsilon)D\).
\(\textbf{Proof}\).
The process can be described as the following event.
Event 1: We randomly throw \(\lvert S \rvert D\) into \([1,r]\) bins. By the principle of balls-and-bins model, we can apply the Chernoff bound to show that with high probability there are \((1-\epsilon)\lvert S \rvert\) non-empty bins.
So, it means that for one particular set \(S\), we have \(\lvert N(S) \rvert \ge (1-\epsilon)\lvert S \rvert D\). By a union bound, it holds with high probability. Then, for all \(S\subseteq L\), it still holds.