[25] An (n, d, , c) OR-concentrator is a bipartite graph G(L+ R, E) on the independent vertex sets L and R with d(L) =

[25] An (n,

d, α,

c) OR-concentrator is a bipartite graph G(L+

R, E) on the independent vertex sets L and R with d(L) = d(R) = n such that (i) every vertex in L has degree

d, and (ii) every subset S ⊆ L with d(S) ≤ αn is connected to at least cn neighbors (in R). Show that there exist (n, 9.48, 1 3 , 2) OR-concentrators.

Comments. A simple incompressibility proof is given by M. Fouz in

[CS798 Course Report, University of Waterloo, December 2007]. A probabilistic proof (with worse constants) is found in [R. Motwani and P.

Raghavan, Randomized Algorithms, Cambridge Univ. Press, 1995, pp.

108–110].