Superconcentrators From Expanders

Today I will be blogging about the construction of superconcentrators from expanders. This is directly from the expanders survey. I am just reviewing it here for my own learning. First some definitions.
Definition 1. A $d-$ regular bipartitie graph $(L,R,E)$, with $|L|=n$ and $|R| =m$ is called a $\emph{magical graph}$ if it saisfies the properties below. For a given set $S$ of vertices, we denote the set of vertices to which some vertex in $S$ is connected as $\Gamma(S)$.

1. For every $S$ with $|S| \leq \frac{n}{10}, |\Gamma(S)| \geq \frac{5d}{8} |S|$
2. For every $S$ with $\frac{n}{10} < |S| \leq \frac{n}{2}$, $|\Gamma(S)| \geq |S|$.

Definition 2. A superconcentrator is a graph $G=(V,E)$ with two given subsets $I, O \subseteq S$ with $|I|=|O|=n$, such that for every $S \subseteq I$ and $T \subseteq O$ with $|S|=|T|=k$, the number of disjoint paths from $S$ to $T$ is at least $k$.

Superconcentrators with $O(n)$ edges are interesting for various reasons which we do not go into here.

But we do give a construction of a superconcentrator with $O(n)$ edges from magical graphs above. A simple probabilistic argument can show the following result.

Theorem There exists a constant $n_0$ such that for every $d \geq 32$, such that $n \geq m,n_0 \geq \frac{3n}{4}$, there is a magical graph with $|L|=n,|R|=m$.

Here is the construction of a superconcentrator from magical graphs. Assume that we can construct a superconcentrator with $O(m)$ edges for every $m \leq (n-1)$. The construction is recursive. First take two copies of the magical graphs $(L_1,R_1,E_1), (L_2,R_2,E_2)$ with $|L_1|=|L_2|=n$ and $|R_1|=|R_2|=\frac{3n}{4}$. Connect every vertex of $L_1$ to the corresponding vertex of $L_2$ and add edges between $R_1=I$ and $R_2=O$ so that the graph becomes a superconcentrator with the size of the input vertex set as $\frac{3n}{4}$. We claim that the resulting graph is a superconcentrator with input vertex set of size $n$.

Identify the input vertex set as $L_1$ and the output vertex set as $L_2$. For every $| S \subseteq L_1 | = k \leq \frac{n}{2}$ it is true that $| \Gamma(S) \cap R_1 | \geq |S|$. Therefore by Halls Marriage Theorem there exists a perfect matching between vertices of $S$ and $\Gamma(S) \cap R_1$. Similarly there exists a perfect matching between vertices of $T \subseteq L_2$ and $\Gamma(T) \cap R_2$. Together with the edges of the superconcentrator between input set $R_1$ and output set $R_2$ there are at least $k$ disjoint paths between $S$ and $T$. It remains to handle the case of $k > \frac{n}{2}$. For $|S|=|T|=k > \frac{n}{2}$, there is a subset $U \subseteq S$ of vertices with $|U| \geq (k - \frac{n}{2})$ such that the vertices corresponding to $U$ in $L_2$ are in $T$. Edges between such vertices contribute to $(k- \frac{n}{2})$ disjoint paths between $S$ and $T$. The remaining $\frac{n}{2}$ disjoint paths exist as proved earlier. Hence we have a superconcentrator with input, output vertex sets of size $n$. How many edges are there in this graph? For the base case of this recursion, we let a superconcentrator with input output sets of size $n \leq n_0$ be the complete bipartite graph with $n_0 ^2$ edges. The following recursion counts the edges. Let $e(k)$ denote the number of edges in the superconcentrator as per this construction with input, output sets of size $k$. Then

$e(k) = k^2$ for $k \leq n_0$ and $e(k) = k + 2dk + e(\frac{3k}{4})$ for $k > n_0$. It can be easily seen that $e(n) \leq Cn$ for $C \geq max(n_0,4(2d+1))$.

2 Responses to Superconcentrators From Expanders

1. Akash Kumar says:

Hello Nirman,

I read your blog and found it curious. Thought that I too will go through the expander survey.

However, I find it confusing that while demonstrating the existence of superconcentrator, you first use the case where you have k n/2?

I mean, if we wanted to use that matching why do not we use it for k > n edges?

2. Akash Kumar says:

Hello Nirman,

(Please ignore the previous post; it has some errors)

I read your blog and found it curious. Thought that I too will go through the expander survey.

However, I find it confusing that while demonstrating the existence of super-concentrator, you first use the case where you have k n/2 edges, you rely upon the matching between L1 and L2 as identified in the survey.

I mean, if we wanted to use that matching why do not we use it for k < n/2 edges as well?

Also I fail to understand why Valiant "ever" conjectured that any super-concentrator must have "much more than" O(n) edges?

Consider the simple bi-partite graph with n-vertices on left and n on right. Each L(i) is joined to R(i). Sure, this graph is disconnected but I guess the definition allows it.