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 .

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?

Please answer if you have time (and patience!) to reply to my (possibly stupid!) queries

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.

Please answer if you have time (and patience!) to reply to my (possibly stupid!) queries