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 regular bipartitie graph , with and is called a if it saisfies the properties below. For a given set of vertices, we denote the set of vertices to which some vertex in is connected as .
1. For every with
2. For every with , .
Definition 2. A superconcentrator is a graph with two given subsets with , such that for every and with , the number of disjoint paths from to is at least .
Superconcentrators with edges are interesting for various reasons which we do not go into here.
But we do give a construction of a superconcentrator with edges from magical graphs above. A simple probabilistic argument can show the following result.
Theorem There exists a constant such that for every , such that , there is a magical graph with .
Here is the construction of a superconcentrator from magical graphs. Assume that we can construct a superconcentrator with edges for every . The construction is recursive. First take two copies of the magical graphs with and . Connect every vertex of to the corresponding vertex of and add edges between and so that the graph becomes a superconcentrator with the size of the input vertex set as . We claim that the resulting graph is a superconcentrator with input vertex set of size .
Identify the input vertex set as and the output vertex set as . For every it is true that . Therefore by Halls Marriage Theorem there exists a perfect matching between vertices of and . Similarly there exists a perfect matching between vertices of and . Together with the edges of the superconcentrator between input set and output set there are at least disjoint paths between and . It remains to handle the case of . For , there is a subset of vertices with such that the vertices corresponding to in are in . Edges between such vertices contribute to disjoint paths between and . The remaining disjoint paths exist as proved earlier. Hence we have a superconcentrator with input, output vertex sets of size . 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 be the complete bipartite graph with edges. The following recursion counts the edges. Let denote the number of edges in the superconcentrator as per this construction with input, output sets of size . Then
for and for . It can be easily seen that for .