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.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s