[37] An (n,

d, m)-graph is a bipartite multigraph with n vertices on the left side and m vertices on the right side, with every vertex on the left having degree

d, and every vertex on the right having degree dn/m (assuming m|dn). An (n,

d, m)-graph is (α, β)-expanding if every subset S of αn vertices on the left has more than βm neighbors on the right, for 0 < α ≤ β < 1. Prove that for every n, 0 < α ≤ β < 1, λ > 0, it suffices to satisfy that d > H(α) + H(β)λ

H(α) − H(α/β)β

to ensure that there is an (α, β)-expanding (n,

d, λn)-graph. Here H is the binary entropy function (Definition 1.11.1 on page 67) defined by H(p) = p log 1/p + (1 − p) log 1/(1 − p) where 0 ≤ p ≤ 1.

Comments. Hint: take a (n,

d, λn)-graph of maximal complexity. Source:

[U. Sch¨oning, Random Struct. Alg., 17(2000), 64–77]. The original probabilistic proof with λ = 1 is in [L.A. Bassalygo, Prob. Inform. Transmission, 17(1981), 206–211].