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)).

This entry was posted on Friday, March 7th, 2008 at 8:08 am and is filed under CS Theory, Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply