Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap

Yonatan Bilu, Nathan Linial

We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let $G$ be a graph on $n$ v…