EXPANDER GRAPHS AND THEIR APPLICATIONS 449 R FIGURE 1.Constructing a super concentrator. of our magical graph,where Lil=n,and Ril =3n/4.(ii)A super concentrator C connecting the input set R to the output set R2.The input,output sets have size 3n/4 and therefore C exists by induction.(iii)A perfect matching between L and L2.The input and output sets of our graph are L and L2 respectively.This is illustrated in Figure 1. We need to prove that the graph we have constructed,C,is indeed a super concentrator and derive an upper bound on the number of its edges.Let S be a set of input vertices and T a set of output vertices such that S=T=k. Ifk≤n/2,then Tc,(S)川≥IS]and rG2((T)川≥lTl,since G,G2 are magical graphs.Hence,by Hall's theorem there exists a perfect matching from S to Ic,(S) and from T to IG(T).Let S'Ic(S)be the set of vertices matched to vertices in S and likewise for T'and T.Since C is a super concentrator,the sets S'and T can be connected by k disjoint paths.Consequently,S and T can be connected by disjoint paths in C. If the two sets S and T are large,i.e.S=T=k>n/2,then there must exist at least k-n/2 vertices in S that are matched to vertices in T by direct matching edges of(iii)above.Therefore we can delete the matched vertices from S and T and reduce the problem to the previous case of k<n/2.It follows that C is a super concentrator. We still need to provide an upper bound on the number of edges e(n)in our n-inputs graph C.We obtain the following recursion: e(n)n2 2nd+n+e(3n/4)for n no forn≤no Solving this recursion yields e(n)<Kn,where K is a constant that depends only on no and d.Therefore we obtained a super concentrator with O(n)edges as required. A word about algorithms to construct such graphs:Suppose that we have an algorithm which constructs magical graphs of left size n in time t(n).It should be clear that the above recursive construction yields an algorithm that constructs a super concentrator with input/output size n in time O(t(n)). Finally,we note that super concentrators are but one example among a host of network construction problems in which expanders serve as a key building block.EXPANDER GRAPHS AND THEIR APPLICATIONS 449 G C 1 G2 L1 R1 R2 L2 Figure 1. Constructing a super concentrator. of our magical graph, where |Li| = n, and |Ri| = 3n/4. (ii) A super concentrator C connecting the input set R1 to the output set R2. The input, output sets have size 3n/4 and therefore C exists by induction. (iii) A perfect matching between L1 and L2. The input and output sets of our graph are L1 and L2 respectively. This is illustrated in Figure 1. We need to prove that the graph we have constructed, C , is indeed a super concentrator and derive an upper bound on the number of its edges. Let S be a set of input vertices and T a set of output vertices such that |S| = |T| = k. If k ≤ n/2, then |ΓG1 (S)|≥|S| and |ΓG2 (T)|≥|T|, since G1, G2 are magical graphs. Hence, by Hall’s theorem there exists a perfect matching from S to ΓG1 (S) and from T to ΓG2 (T). Let S ⊆ ΓG1 (S) be the set of vertices matched to vertices in S and likewise for T and T. Since C is a super concentrator, the sets S and T can be connected by k disjoint paths. Consequently, S and T can be connected by disjoint paths in C . If the two sets S and T are large, i.e. |S| = |T| = k > n/2, then there must exist at least k − n/2 vertices in S that are matched to vertices in T by direct matching edges of (iii) above. Therefore we can delete the matched vertices from S and T and reduce the problem to the previous case of k ≤ n/2. It follows that C is a super concentrator. We still need to provide an upper bound on the number of edges e(n) in our n-inputs graph C . We obtain the following recursion: e(n) ≤  2nd + n + e (3n/4) for n>n0 n2 for n ≤ n0 . Solving this recursion yields e(n) ≤ Kn, where K is a constant that depends only on n0 and d. Therefore we obtained a super concentrator with O(n) edges as required. A word about algorithms to construct such graphs: Suppose that we have an algorithm which constructs magical graphs of left size n in time t(n). It should be clear that the above recursive construction yields an algorithm that constructs a super concentrator with input/output size n in time O(t(n)). Finally, we note that super concentrators are but one example among a host of network construction problems in which expanders serve as a key building block