Monotone expansion

This work presents an explicit construction of a family of monotone expanders, which are bi-partite expander graphs whose edge-set is defined by (partial) monotone functions. The family is essentially defined by the Mobius action of SL 2 (R), the group of 2 x 2 matrices with determinant one, on the interval [0,1]. No other proof-of-existence for monotone expanders is known, not even using the probabilistic method. The proof extends recent results on finite/compact groups to the non-compact scenario. Specifically, we show a product-growth theorem for SL 2 (R); roughly, that for every A ⊂ SL 2 (R) with certain properties, the size of AAA is much larger than that of A. We mention two applications of this construction: Dvir and Shpilka showed that it yields a construction of explicit dimension expanders, which are a generalization of standard expander graphs. Dvir and Wigderson proved that it yields the existence of explicit pushdown expanders, which are graphs that arise in Turing machine simulations.

Authors

• Jean Bourgain
• Amir Yehudayoff

Keywords

• expander graphs
• explicit constructions