## Notes of Zeev Dvir’s talk

Monotone expanders – constructions and applications

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

1. Constructions

1.1. ${\log n}$ degree

Dvir and Shpilka. Use shift, i.e. translation in ${{\mathbb Z}/n{\mathbb Z}}$.

Wigdersion-Xiao give an algorithm that constructions ${O(\log n)}$ shifts that expand every set in ${{\mathbb Z}/n{\mathbb Z}}$.

1.2. ${\log\log\cdots\log n}$ degree

Arbitrary constant number of logs. Start with previous graph and reduce degree to ${\log\log n}$ by applying replacement product.

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

Alon, Schwartz and Shapira show that out of a monotone expander of size ${n}$, one can extract a bounded degree monotone expander of size ${\log\log n}$. 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 ${c_0 >0}$ and ${d}$ monotone increasinf functions ${f_i :[0,1]\rightarrow[0,1]}$ such that the union of the images of any set by ${f_i}$ has Lebesgue measure ${\geq (1+\epsilon)|S|}$.

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 ${[0,1]}$, they are monotone). This is a ${SL_2 ({\mathbb R})}$ action, which has a spectral gap. Use an element ${z=g_1 +g_1^{-1}+\cdots+g_m +g_m^{-1}}$ with ${g_i}$‘s very close to ${1}$. They nearly map ${[0,1]}$ to ${[0,1]}$. Using Breuillard’s strong Tits alternative, one can assume ${g_i}$‘s generate a free group. $\Box$

2. Applications

2.1. Dimension expanders

Definition 2 A set of ${d}$ linear maps ${T_i}$ in dimension ${n}$ is a dim expander if for every subspace ${V}$ of at most middle dimension,

$\displaystyle \begin{array}{rcl} \mathrm{dim}(\sum_{i}T_i (V))\geq (1+\epsilon)\mathrm{dim}(V). \end{array}$

Easy to produce by the probabilistic method.

[Lubotzky, Zelmanov 2004]: Explicit construction in characteristic ${0}$.

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

For a monotone map ${f:[n]\rightarrow[n]}$, let it act on basis vectors, gives linear map ${T_f :F^n \rightarrow F^n}$, any field. Define the pivot of a vector as the highest nonzero coordinate. Then ${T_f}$ commutes with pivot, and this allows to relate expansion to dim expansion.

2.2. ${d}$-page graphs

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

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

$\displaystyle \begin{array}{rcl} NTIME(n)\not=DTIME(n). \end{array}$

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

[Dvir, Shpilka 2005]: Degree ${d}$ monotone expanders give rise to ${d}$-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.