448 SHLOMO HOORY,NATHAN LINIAL,AND AVI WIGDERSON ()<(ne/k),we get that: P∑Xs,T>0≤∑PrXs,T=1刂= ∑t/m)d S.T S.T S.T n/10d sd m 5ds 5ds/8 8m n/10d 5ds/8 () 8me 5ds ≤ 5ds <1/10. 8m 8=1 The last inequality follows since the s-th term is bounded by 20-. Similarly,we bound the probability of violating the second property by an anal- ogous expression,which is simpler to bound.For every S C L with cardinality 10a<s=ISI<2,and T C R with t=T<S],let Ys.T be an indicator random variable for the event that all the edges from S go to T.As before,we would like to prove that the probability of the event >Ys.r=0 is small: n/2 P∑Xsr>0≤∑PWsr=-∑/m)4≤ (s/m)sd S,T S.T s.7 s=n/10d n/2 ≤ ∑[me/s)·(me/s)·(s/m)9°<1/10. 8= As before,the last inequality follows by noting that for all s the quantity in square brackets is bounded by 10-4.Therefore,most graphs are(n,m;d)-magical graphs. We now turn to the solution of the three problems presented above.Note that Lemma 1.9 is existential,whereas we need explicit constructions of magical graphs to resolve our three problems.The issue of explicit constructions is an important aspect of this field and of this article,but at present we show how to solve these problems using the existence of magic graphs as a "black box". 1.3.The three solutions. 1.3.1.A super concentrator with O(n)edges.We will see how magical graphs allow us to construct super concentrators.These graphs exhibit incredibly high connec- tivity despite the fact that they have only O(n)edges.There is a long and still ongoing search for super concentrators with n input and output vertices and Kn edges with K as small as possible.This "sport"has motivated quite a few im- portant advances in this area.The current "world record"holders are Alon and Capalbo [AC04]. If G is an (n,3n/4;d)-magical graph,then r(S)>S for every S CL with S]<2.By Hall's marriage theorem (e.g.,[Die97,Theorem 2.1.2]),for every SCL of sizeS<there is a perfect matching from S to r(S). We use this fact to recursively construct a super concentrator C with n vertices on each side.For n below no,simply observe that a complete bipartite graph is a super concentrator with n2 edges. For n no we construct a super concentrator C with n inputs and outputs, using three building blocks:(i)Two copies G1=(L1,R1,E1)and G2=(L2,R2,E2)448 SHLOMO HOORY, NATHAN LINIAL, AND AVI WIGDERSON n k ≤ (ne/k)k, we get that: Pr[ S,T XS,T > 0] ≤  S,T Pr[XS,T = 1] =  S,T (t/m) sd ≤ n/  10d s=1  n s  m 5ds/8  5ds 8m sd ≤ n/  10d s=1 ne s s 8me 5ds 5ds/8 · 5ds 8m sd < 1/10. The last inequality follows since the s-th term is bounded by 20−s. Similarly, we bound the probability of violating the second property by an anal￾ogous expression, which is simpler to bound. For every S ⊂ L with cardinality n 10d < s = |S| ≤ n 2 , and T ⊂ R with t = |T| < |S|, let YS,T be an indicator random variable for the event that all the edges from S go to T. As before, we would like to prove that the probability of the event
YS,T = 0 is small: Pr[ S,T YS,T > 0] ≤  S,T Pr[YS,T = 1] =  S,T (t/n) sd ≤  n/2 s=n/10d n s m s  (s/m) sd ≤  n/2 s=1 (ne/s) · (me/s) · (s/m) d s < 1/10. As before, the last inequality follows by noting that for all s the quantity in square brackets is bounded by 10−4. Therefore, most graphs are (n,m; d)-magical graphs.
We now turn to the solution of the three problems presented above. Note that Lemma 1.9 is existential, whereas we need explicit constructions of magical graphs to resolve our three problems. The issue of explicit constructions is an important aspect of this field and of this article, but at present we show how to solve these problems using the existence of magic graphs as a “black box”. 1.3. The three solutions. 1.3.1. A super concentrator with O(n) edges. We will see how magical graphs allow us to construct super concentrators. These graphs exhibit incredibly high connec￾tivity despite the fact that they have only O(n) edges. There is a long and still ongoing search for super concentrators with n input and output vertices and Kn edges with K as small as possible. This “sport” has motivated quite a few im￾portant advances in this area. The current “world record” holders are Alon and Capalbo [AC04]. If G is an (n, 3n/4; d)-magical graph, then |Γ(S)|≥|S| for every S ⊂ L with |S| ≤ n 2 . By Hall’s marriage theorem (e.g., [Die97, Theorem 2.1.2]), for every S ⊆ L of size |S| ≤ n 2 there is a perfect matching from S to Γ(S). We use this fact to recursively construct a super concentrator C with n vertices on each side. For n below n0, simply observe that a complete bipartite graph is a super concentrator with n2 edges. For n ≥ n0 we construct a super concentrator C with n inputs and outputs, using three building blocks: (i) Two copies G1 = (L1, R1, E1) and G2 = (L2, R2, E2)