The main purpose of this work is to formally define monotone expanders and motivate their study with (known and new) connections to other graphs and to several computational and pseudorandomness problems. In particular we explain how monotone expanders of constant degree lead to:(1) Constant degree dimension expanders in finite fields, resolving a question of [BISW].(2) O(1)-page and O(1)-pushdown expanders, resolving a question of [GKS86], and leading to tight lower bounds on simulation time for certain Turing Machines.

Bourgain [Bou09] gave recently an ingenious construction of such constant degree monotone expanders. The first application (1) above follows from a reduction in [DS07]. We give a short exposition of both construction and reduction.

The new contributions of this paper are simple. First, we explain the observation leading to the second application (2) above, and some of its consequences. Second, we observe that a variant of the zig-zag graph product preserves monotonicity, and use it to give a simple alternative construction of monotone expanders, with near-constant degree