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.
Dvir and Shpilka. Use shift, i.e. translation in .
Wigdersion-Xiao give an algorithm that constructions shifts that expand every set in .
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.1. Dimension expanders
Definition 2 A 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.