**Monotone expanders – constructions and applications**

A monotone expander is a bipartite graph embedded in the plane with 2 columns of vertices, joined by collections of pairwise nonintersecting edges.

**1. Constructions **

** 1.1. degree **

Dvir and Shpilka. Use shift, i.e. translation in .

Wigdersion-Xiao give an algorithm that constructions shifts that expand every set in .

** 1.2. degree **

Arbitrary constant number of logs. Start with previous graph and reduce degree to by applying replacement product.

Replacement product (goes back to Gromov 1983). Given graphs and , blow up each vertex into a copy of , carefully relink edges. If both and are expanders, so is . Construction preserves monotonicity.

Alon, Schwartz and Shapira show that out of a monotone expander of size , one can extract a bounded degree monotone expander of size . This might be used to construct explicitely bounded degree monotone expander, in a simpler manner than in the next section.

** 1.3. Bounded degree **

This is due to Bourgain. Uses expansion in linear groups. Very involved. Main step of proof is

Lemma 1 (Bourgain)There exists and monotone increasinf functions such that the union of the images of any set by has Lebesgue measure .

Then discretize these functions to produce monotone expander.

*Proof:* of Lemma. Use homographies of the real projective line (we shall only use those without a pole in , they are monotone). This is a action, which has a spectral gap. Use an element with ‘s very close to . They nearly map to . Using Breuillard’s strong Tits alternative, one can assume ‘s generate a free group.

**2. Applications **

** 2.1. Dimension expanders **

Definition 2A set of linear maps in dimension is a dim expander if for every subspace of at most middle dimension,

Easy to produce by the probabilistic method.

**[Lubotzky, Zelmanov 2004]**: Explicit construction in characteristic .

**[Dvir, Shpilka 2005]**: Will follow from monotone expanders, over any field.

For a monotone map , let it act on basis vectors, gives linear map , any field. Define the pivot of a vector as the highest nonzero coordinate. Then commutes with pivot, and this allows to relate expansion to dim expansion.

** 2.2. -page graphs **

**[Buss, Shor 1984]**: Order vertices on the spine of a -page book. Draw nonintersecting edges on each page (edges can have common vertices). This is a -page graph. Define the page number of a graph.

**[Pippenger 1982]**: If edges are disjoint even at vertices, speak of -pushdown graph. Such graphs come up in linear time complexity, in the proof that

**Question**: Expansion of such graphs ? This is related to tight simulation bounds for non deterministic

**[Dvir, Shpilka 2005]**: Degree monotone expanders give rise to -pushdown graphs.

Indeed, distort vertices in 2 columns joined by a layer of non intersecting edges into a page.

** 2.3. Open problems **

How good expanders can monotone graphs be ?

Find simpler constructions.