Authors Zeev Dvir, Avi Wigderson,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308
www.theoryofcomputing.org
RESEARCH SURVEY
Monotone Expanders:
Constructions and Applications
Zeev Dvir∗ Avi Wigderson∗
Received: February 4, 2010; published: December 30, 2010.
Abstract: 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 Barak,
Impagliazzo, Shpilka, and Wigderson (2004);
2. O(1)-page and O(1)-pushdown expanders, resolving a question of Galil, Kannan, and
Szemerédi (1986) and leading to tight lower bounds on simulation time for certain
Turing Machines.
Recently, Bourgain (2009) gave a rather involved construction of such constant-degree
monotone expanders. The first application (1) above follows from a reduction due to Dvir
and Shpilka (2007). We sketch Bourgain’s construction and describe the 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
∗ Research partially supported by NSF grants CCF-0832797 and DMS-0835373.
ACM Classification: F.1.3, G.2.2
AMS Classification: 68Q15, 68R10
Key words and phrases: expander, zig-zag, k-page graphs, pushdown graphs
2010 Zeev Dvir and Avi Wigderson
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2010.v006a012
Z EEV DVIR AND AVI W IGDERSON
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 (c-times iterated log for
any c) degree.
1 Introduction
Expander graphs are families of highly connected sparse graphs. These combinatorial objects have found
numerous applications in diverse areas of mathematics and computer science and have drawn an enormous
amount of attention (see [14] for a survey). Many of the applications require explicit constructions of such
graphs, where “explicit” means graphs that can be constructed by an algorithm that runs in polynomial
time in the size of the graph. Some applications require a more restrictive notion of explicitness in which
the i-th neighbor of a vertex can be computed in time polylogarithmic in the size of the graph. Such
constructions are called “strongly explicit.”
It is easy to show that a random sparse graph is an expander, but proving that some explicit graph
is an expander is considerably harder. Today there are many known constructions of expander graphs
ranging from group theoretic constructions (e. g., [19, 22, 15]) to purely combinatorial ones [26, 2].
The question of whether restricted classes of graphs can be expanders of constant degree has also
received attention, and there are many negative examples for natural classes, e. g., planar graphs (and
graphs with other excluded minors) [18, 3] and Cayley graphs of Abelian and near-Abelian groups [16, 20].
More relevant to us are the classes of k-page graphs and k-pushdown graphs (which we define later) that
arise as computation graphs of Turing machines, for which the expansion question remained open and is
key to resolving some complexity questions [12, 27].
The focus of this paper are monotone graphs and their expansion properties. Monotone graphs are
defined by monotone mappings. Throughout the paper the vertex set of graphs will be [n], the first n
integers with their natural ordering. A partial monotone function f : [n] → [n] satisfies f (x) > f (y) for
all pairs x > y for which the function is defined. Such a function defines a 1-monotone graph whose
edges are all pairs (i, f (i)) for all i ∈ Dom( f ). Similarly, d monotone partial functions f1 , . . . , fd define a
d-monotone graph. This graph is the union of the d 1-monotone graphs defined by the functions f1 , . . . , fd .
Note that such graphs have in-degree, as well as out-degree, at most d. The most natural way to think
of these graphs is as bipartite directed graphs with n left vertices and n right vertices and edges going
from left to right.1 In this setting a graph is expanding if every set of size t ≤ n/2 of left vertices has at
least (1 + α) · t neighbors for some constant α > 0. Monotonicity (with degree d) is equivalent to saying
that the set of edges can be partitioned into d disjoint monotone matchings (that is, in each matching the
edges do not cross).
Unlike the question in general graphs, there is no obvious way of even proving the existence of
d-monotone expanders for small d. Attempting the probabilistic method one is faced with the choice
of distribution on monotone mappings, and then with the analysis. One fundamental problem seems
to be that there are only exp(O(n)) partial monotone mappings on [n], whereas there are exp(n log(n))
unrestricted mappings. While it is trivial to prove that O(1) random mappings create an expander with
high probability, we have no analogous result for monotone mappings. To give an example of the difficulty
1 One can easily make the transition to the usual undirected case by including the inverse functions as well.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308 292
M ONOTONE E XPANDERS : C ONSTRUCTIONS AND A PPLICATIONS
of analyzing a random monotone construction consider the following natural way of sampling a monotone
mapping: pick two sets S, T ⊂ [n] of size n/2 uniformly at random and map S onto T in a one-to-one way
(mapping the i-th element of S to the i-th element of T ). It is easy to see that the set [1,t] will not expand
√
with high probability for t = Ω(n) since this set will have all of its neighbors in the interval [1,t + O( n)]
with high probability.
Let us return to explicit constructions (which are more interesting for applications anyway). The
first construction of monotone expanders was given in [11] in connection with dimension expanders;
we shall elaborate on this connection below. This construction has logarithmic degree and is composed
mainly of shift maps (that is, maps of the form f (x) = x + i). This construction was recently significantly
improved by Bourgain in [6] where he constructs optimal O(1)-monotone expanders. In this work, we
construct O(log(c) n)-monotone expanders for every integer c (with log(c) (·) denotes the c-times iterated
logarithm). Bourgain’s construction is quite involved, using in particular the recent breakthrough on the
“Tits Alternative” by Breuillard [8], and its analysis is even more involved, extending work on spectral
gaps on the unitary group SU(2) by Bourgain and Gamburd [7] to the group SL2 (R) (the reference [6]
contains only sketches of the construction and analysis). In Section 6 we provide some more details on
the workings behind this theorem.
Theorem 1.1 (Bourgain [6]). There exists a strongly-explicit family of constant-degree monotone ex-
panders.
We will give our (suboptimal) construction here for two reasons. First, it is simple: it uses an iterated
replacement product [26], observing that with appropriate ordering of vertices it preserves monotonicity
of its components. Second, it shows that any (even nonconstructive) existence proof of O(1)-monotone
expanders can be used as a base graph (in the style of [2]) to make our construction a strongly-explicit
one of O(1)-monotone expanders.
1.1 Monotone expanders and dimension expanders
Monotone graphs, and the question of their expansion for small d arose implicitly in the paper of Dvir and
Shpilka [11]. They reduce the problem of constructing degree-d dimension expanders (proposed in [4])
to the construction of O(d)-monotone expanders, and give an explicit construction of O(log n)-monotone
expanders of size n, leaving possible improvements as an open question. Since this connection was never
given explicitly, we sketch it below.
A degree-d dimension expander is a set of d linear mappings T1 , . . . , Td : Fn → Fn such that for every
linear subspace V ⊂ Fn with dim(V ) ≤ n/2 we have
!
d
dim ∑ Ti (V ) ≥ (1 + α) · dim(V ) .
i=1
Here, F is a field, possibly finite, and α is a positive constant independent of n. The probabilistic method
shows that families of constant-degree dimension expanders exist. An explicit construction over fields of
characteristic zero was given in [21].2 Here, by ”explicit” we mean that the matrices computing the linear
2 The same result was obtained independently in [13] in the context of quantum expanders which imply dimension expanders
over characteristic zero.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308 293
Z EEV DVIR AND AVI W IGDERSON
maps can be described as the output of an algorithm which runs in time polynomial in n (the notion of a
“strongly-explicit” dimension expander does not make sense). In [11] an approach toward constructing
dimension expanders over arbitrary fields was given. This approach involved applying a monotone
expander graph on the coordinates (that is, permute the coordinates using d monotone mappings).
Theorem 1.2 ([11]). If there exists an explicit construction of d-monotone expander graphs than there is
an explicit construction of degree-d dimension expanders over any field F.
Proof. Let e1 , . . . , en ∈ Fn denote the standard basis vectors. For each monotone partial function f : [n] →
[n] in the expander we define a linear map L f : Fn → Fn as follows: L f (ei ) = e f (i) if f (i) is defined and
L f (ei ) = 0 otherwise. To see why these linear maps are a dimension expander consider a subspace V ⊂ Fn
of dimension t ≤ n/2. For a non-zero vector v ∈ Fn denote by π(v) ∈ [n] the largest index of a non-zero
coordinate of v. Similarly, let π(V ) = {π(v) | v ∈ V }. Observe that |π(V )| = dim(V ) = t. Monotonicity
implies that
π(L f (V )) ⊇ f (π(V )) ,
where, for a set S, f (S) is defined as the set of all images of f on elements of S on which f is defined. So,
using expansion we obtain that !
d
π ∑ L f (V )
i ≥ (1 + α) · t
i=1
giving the required bound on the dimension.
This theorem combined with Bourgain’s construction gives explicit constant-degree dimension
expanders over any field.
Corollary 1.3. Over any field F, there exists an explicit family of constant degree dimension expanders.
1.2 Monotone graphs and multi-pushdown graphs
The second contribution of this paper is the observation of a simple connection between d-monotone
graphs and d-pushdown graphs: if the former are expanding then so are the latter (for the same d).
This is of consequence since the question of whether O(1)-pushdown graphs have small separators
(and thus cannot be expanders) is intimately related (and in some cases equivalent) to several questions
in Turing machine complexity. With this observation, Bourgain’s result simultaneously proves some
conjectures and refutes others in one shot. The fundamental connection to complexity arises from the
basic fact [24, 23] that computation graphs of certain Turing machines are O(1)-pushdown graphs. We
describe this connection and its consequences below.
A d-pushdown graph [24, 23] is a graph on an ordered set of vertices such that, if we order the vertices
along the spine of a book, the edges can be drawn on d pages of the book such that on each page, the
edges are disjoint (they do not even share a vertex). These graphs come up naturally as the computation
graphs of Turing machines with d tapes and are also a natural subclass of d-page graphs [9]. For a formal
definition of d-pushdown graphs see Section 5.
Let us recall the definition of a separator. A separator S is a subset of the vertices of a graph G on n
vertices such that the vertices outside S can be partitioned into two disjoint sets A and B each of size at
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308 294
M ONOTONE E XPANDERS : C ONSTRUCTIONS AND A PPLICATIONS
most 2n/3 and such that there are no edges between A and B. Observe that a graph with a sublinear-size
√
separator is not an expander. The planar separator theorem [17] says that a planar graph has a O( n)-size
separator. Since d-pushdown graphs are a generalization of planar graph it is natural to ask whether or
not such graphs have o(n) separators. This question (conjectured to be true in [24]) turns out to be related
to the time needed to simulate a deterministic TM by a nondeterministic one.3 A “segregator” theorem
(proving the existence of a weaker object than a separator) is the combinatorial “heart” of the celebrated
separation [23] of nondeterministic linear time from deterministic linear time (see also [27] for more
recent results in this spirit).
In [12] it was shown that there exist 3-pushdown graphs which are “almost” expanders, in the sense
that every separator must be of size Ω(n/ log(c) (n)) for any constant c. This is probably the earliest
occurrence of what is now referred to as an iterative “Zig-Zag” construction. Our construction of
degree-log(c) (n) monotone expanders is very similar to theirs. In this paper we observe that d-monotone
expanders can easily be transformed into d-pushdown expanders. Combining this observation with
Bourgain’s result we obtain that there exist (explicit) d-pushdown graphs which are expanders, settling an
old open problem. We prove the following theorem in Section 5.
Theorem 1.4. If there exist (strongly-explicit) d-monotone expanders than there exist (strongly-explicit)
d-pushdown expanders.
In [27] the assumption that the class of d-pushdown graphs have sub-linear separators was used to
derive several complexity theoretic results. In particular, it was shown in [27] that this assumption implies
the separation
NTIME(t) 6= Σ4 −TIME(t)
for all time bounds t. The existence of expanding d-pushdown graphs shows that this approach to prove
such a separation cannot succeed.
Lower bounds on simulation time It was shown in [12] that the question of whether d-pushdown
graphs are separable or not (i. e., if these graphs have sublinear-size separators) is equivalent to a question
regarding the simulation time of certain Turing machines. More formally, let t(n) denote the time it takes
a 1-tape online nondeterministic TM to simulate a two tape real-time nondeterministic TM.4 One can
easily show that t(n) = O(n2 ). The question of whether or not t(n) = o(n2 ) was shown in [12] to be
equivalent to whether or not d-pushdown graphs have small (sublinear) separators. Combining Bourgain’s
result with Theorem 1.4 above we obtain the following corollary.
Corollary 1.5. In the notation above, we have t(n) = Θ(n2 ).
1.3 Organization
In Section 2 we give formal definitions and notation that will be used later on. In Section 3 we give the
analysis of the replacement product for monotone graphs. In Section 4 we describe our iterative con-
struction of near-constant-degree monotone expanders. In Section 5 we explain the connection between
3 These results very strictly depend on the sequential access in a multi-tape Turing machine. They do not apply even if we
replace the linear tape by a 2-dimensional grid, let alone with random access.
4 A real time TM reads a new symbol at each step and an on-line TM is such that the input tape is one-way.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308 295
Z EEV DVIR AND AVI W IGDERSON
monotone and multi-pushdown graphs. Section 6 contains a brief outline of Bourgain’s construction
of monotone expanders. We conclude in Section 7 with some open problems and directions for future
research.
2 Preliminaries and notation
We denote [n] = {1, 2, . . . , n}. All logarithms are base 2.
Let V be a finite totally ordered set. We denote by Part[V ] the set of partial functions f : V → V ∪ {⊥}
on the set V ; here f (x) = ⊥ means that f is undefined at x. We say that f ∈ Part[V ] is monotone if,
whenever f is defined at two distinct points x < y ∈ V , we have f (x) < f (y). (In this paper we use
“monotone” to mean “strictly increasing.”) Notice that if f is monotone it is also injective and so there
exists a (partial) inverse f −1 ∈ Part[V ] which is also monotone. Also, if f , g ∈ Part[V ] are monotone
then we can define their composition f ◦ g which is also monotone (the composition is defined on those
points x where g(x) 6= ⊥ and f (g(x)) 6= ⊥).
An ordered directed graph is a pair G = (V, ( f1 , . . . , fd )) with V a finite totally ordered set and
fi ∈ Part[V ] where we think of fi (x) as mapping x to its i-th neighbor (if one exists). In the following we
will refer to these simply as “graphs.” We will call d the degree of the graph. A graph G = (V, ( f1 , . . . , fd ))
is monotone if for all i ∈ [d], fi is monotone (with respect to the ordering of V ). Notice that if G is
monotone then for all x ∈ V , degin (x) ≤ d (since the functions fi are injective). Let G = (V, ( f1 , . . . , fd ))
−1
be a monotone graph. We say that G is inverse-closed if d is even and for all i ∈ [d/2], f2i = f2i−1 (that
is, G is composed of d/2 neighbor functions and their d/2 inverses).
For a graph G = (V, ( f1 , . . . , fd )) and a subset S ⊂ V we denote the boundary of S in G as
∂G S , {(x, i) | x ∈ S, fi (x) ∈ V \ S} .
(We omit the subscript G if it is clear from the context.) The edge-expansion of G is denoted by
|∂G S|
h(G) , min .
S⊂V d · |S|
1≤|S|≤ 21 |V |
Another notion of expansion is vertex-expansion. For S ⊂ V let
ΓG (S) , {y ∈ V | (∃x ∈ S, i ∈ [d])( fi (x) = y)} .
The vertex expansion of G, denoted µ(G), is5
|ΓG (S) \ S|
µ(G) , min .
S⊂[n] |S|
1≤|S|≤ 12 |V |
Claim 2.1. If G is monotone then µ(G) ≥ h(G).
5 Notice that this definition is slightly different from the way monotone expanders were defined in the Introduction. However,
the two definitions are equivalent up to a constant factor.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308 296
M ONOTONE E XPANDERS : C ONSTRUCTIONS AND A PPLICATIONS
Proof. Let |S| ≤ |V |/2. Then S has at least h(G) · d · |S| edges leaving it. Since G is monotone, the
in-degree of a vertex is at most d and so there have to be at least h(G) · |S| neighbors of S that are not in
S.
We will require the following simple observation.
Claim 2.2. If G = (V, ( f1 , . . . , fd )) is a monotone inverse-closed graph, then for all sets S ⊂ V we have
|∂G S| ≥ h(G) · d · min{|S|, |V | − |S|} .
Proof. The inequality follows from the definition of h(G) and from the fact that, in an inverse-closed
graph, the number of edges from any set S to its complement is equal to the number of edges in the
opposite direction.
3 The replacement product of monotone graphs
Let V1 ,V2 be two finite totally ordered sets. The reverse lexicographic ordering of the set V1 × V2 is
defined as follows: (a1 , a2 ) > (b1 , b2 ) if a2 > b2 or, a2 = b2 and a1 > b1 .
Let G1 = (V1 , ( f1 , . . . , fD )) and G2 = (V2 , (g1 , . . . , gd )) be two graphs such that |V2 | = D. The re-
placement product G1 ◦ G2 is a graph with vertex set V1 ×V2 , ordered according to reverse lexicographic
ordering and with 2d neighbor functions s1 , . . . , sd ,t1 , . . . ,td ∈ Part[V1 × V2 ] defined as follows: For
i ∈ [d],
si (a1 , a2 ) = (a1 , gi (a2 ))
(if gi (a2 ) = ⊥ then si (a1 , a2 ) = ⊥). The functions t1 , . . . ,td are all equal to the same function
t(a1 , a2 ) = ( fa2 (a1 ), a2 ) ,
where the set V2 is identified in some arbitrary one-to-one way with [D] (again, if fa2 (a1 ) = ⊥ then
t(a1 , a2 ) = ⊥). It is clear from the definitions that, if G1 and G2 are monotone, then so is their product
G1 ◦ G2 . The reason for including many parallel edges in the definition will make sense later when we
argue about the expansion properties of the replacement product of two expanders (this is necessary to
avoid small cuts).
The proof of the following lemma, bounding the edge-expansion of the replacement product, is
essentially the same as the proof for undirected graphs appearing in [2]. Since our definitions are more
involved we retrace the argument below.
Lemma 3.1 (Replacement product of two monotone expanders). Let G1 = (V1 , ( f1 , . . . , fD )) and G2 =
(V2 , (g1 , . . . , gd )) be two monotone inverse-closed graphs such that |V2 | = D. Let H = G1 ◦ G2 . Then H is
a monotone graph (with respect to reverse lexicographic ordering) and
1
ah(H) ≥ · h(G1 )2 · h(G2 ) .
80
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308 297
Z EEV DVIR AND AVI W IGDERSON
Proof. As was observed before, if G1 and G2 are monotone then so is G1 ◦ G2 . We are thus concerned
only with bounding the edge expansion.
Let us denote n = |V1 |, δ1 = h(G1 ), δ2 = h(G2 ). Let S ⊂ V1 ×V2 be such that
1 1
|S| ≤ |V1 ×V2 | = · nD .
2 2
Since the degree of H is 2d we need to show that |∂ S| ≥ (1/80)δ12 δ2 · 2d · |S|.
For x ∈ V1 we define Sx = S ∩ ({x} ×V2 ). Let
I 0 = {x ∈ V1 | |Sx | ≤ (1 − δ1 /4)D}
and let I 00 = V1 \ I 0 . We partition the set S into two parts, S0 = x∈I 0 Sx and S00 = S \ S0 .
S
We separate the analysis into two cases. The first is when |S0 | ≥ (1/10)δ1 |S|. In this case we will
get expansion using the mappings that act on the disjoint copies of V2 . For every x ∈ I 0 we have (using
Claim 2.2) that
1
|∂G2 Sx | ≥ δ2 · d · min{|Sx |, D − |Sx |} ≥ δ1 δ2 · d|Sx | ,
4
(we abuse notation and treat Sx as a subset of V2 ). Therefore, using the bound on |S0 |, we obtain that
1 1
|∂H S| ≥ δ1 δ2 · d · |S0 | ≥ · δ 2 δ2 · 2d · |S| .
4 80 1
We now turn to the case when |S0 | < (1/10)δ1 |S|. In this case we have |S00 | ≥ (1 − δ1 /10) · |S|. We
will get expansion using the d identical copies of the map t(x, y) = ( fy (x), y). Since for all x ∈ I 00 we have
|Sx | > (1 − δ1 /4) · D we obtain that
|S00 | |S00 |
≤ |I 00 | ≤ .
D (1 − 41 δ1 ) · D
In particular, since |S00 | ≤ |S| ≤ (1/2) · nD, we have |I 00 | ≤ (2/3) · n. Therefore, by Claim 2.2, we have
1
M = |∂G1 I 00 | ≥ δ1 · D · |I 00 | .
2
Consider the corresponding d · M edges in H. Of these d · M edges at most (1/4)δ1 dD · |I 00 | come from
outside S00 and so there are at least (1/4)δ1 dD · |I 00 | edges from S00 . Among these edges, at most d · |S0 |
can land in S0 (here we rely on the fact that G1 is monotone and so the mappings acting on the copies of
V1 are injective). We can bound this number of edges by
1 1
d · |S0 | ≤ δ1 · d · |S| ≤ δ1 · dD|I 00 | .
10 6
We can therefore conclude that the number of edges from S00 to the complement of S is at least
1 1 1
δ1 · dD · |I 00 | − δ1 · dD · |I 00 | = δ1 · dD · |I 00 | .
4 6 12
As |I 00 | ≥ |S00 |/D and |S00 | ≥ (1/2)|S| we have at least (1/48)δ1 · 2d · |S| edges in H leaving S.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308 298
M ONOTONE E XPANDERS : C ONSTRUCTIONS AND A PPLICATIONS
4 An iterative construction with near optimal degree
In this section we describe a simple iterative construction of monotone expanders with almost constant
degree. We give our construction in two parts. The first (Section 4.1) gives a construction of a monotone
expander with polylogarithmic degree. The second (Section 4.2) shows how to iterate the construction,
using the tools from Section 3, and reduce the degree to log(c) (n) for any constant c.
4.1 The base graph
In this section we describe a construction of a monotone expander graph with polylogarithmic degree
which will be the basis of the full construction. The graph we will use is similar to the one used in [11].
However, since we are shooting for a strongly explicit graph, we will refrain from using the base graph
from [29] (which is not strongly explicit) and will use the explicit expanders implicit in [1, 25] instead.
The degree of these graphs is polylogarithmic (instead of logarithmic as in [29]) but this difference will
“disappear” in the recursion done in the next section.
Theorem 4.1 (Expanders for Zn [1, 25]). There exists a constant h0 > 0 and a strongly explicit family of
graphs
An = ({0, 1, . . . , n − 1}, ( f1 , . . . , fd ))
with d = log(n)O(1) , h(G) ≥ h0 and such that for each i there exists an integer ai such that fi (x) = x + ai
mod n.
We now turn the above graph into a monotone expander in a manner similar to [11]. In fact, the
proof of the following theorem implies that any Cayley expander for Zn with degree d gives a monotone
expander with degree 2d.
Theorem 4.2 (Monotone expander with polylog degree). There exists a constant h1 > 0 and a strongly
explicit family of monotone, inverse-closed graphs
Bn = ({0, 1, . . . , n − 1}, (g1 , . . . , gd ))
with d = log(n)O(1) and h(G) ≥ h1 .
Proof. Without loss of generality suppose n is even (otherwise we can run the construction on n − 1
vertices and then connect a single vertex arbitrarily). Let m = n/2 and let
Am = ({0, 1, . . . , m − 1}, ( f1 , . . . , fd 0 ))
be the graph given by Theorem 4.1. Let a1 , . . . , ad 0 be integers such that, for 0 ≤ x ≤ m − 1,
fi (x) = x + ai mod m .
We define the graph Bn on vertex set {0, 1, . . . , n − 1} to have d = 2d 0 neighbor functions. The first d 0
functions, call them g1 , . . . , gd 0 will be defined as
(
x + ai x ≤ m − 1;
gi (x) =
⊥ otherwise.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308 299
Z EEV DVIR AND AVI W IGDERSON
Since we can assume without loss of generality that the integers ai are smaller than m we have that the
mappings gi , i ∈ [d 0 ] are indeed monotone. We now add to Bn another d 0 mappings gd 0 +1 , . . . , g2d 0 which
will all be the same and will be defined as
(
x − m x ≥ m;
gi (x) =
⊥ otherwise.
It is clear that the graphs Bn are monotone, have degree log(n)O(1) , and are strongly explicit. We can also
assume without loss of generality that Bn is inverse closed simply by adding all the inverses (this will
decrease the edge expansion by at most half). We now bound the edge expansion of Bn .
Let S ⊂ {0, 1, . . . , n − 1} be such that |S| ≤ n/2. We will show that the number of edges leaving S is
at least (1/16) · h0 · d · |S|. Define S1 = S ∩ {0, 1, . . . , m − 1} and S2 = S \ S1 . We separate the analysis
into two cases based on the size of the set
I = S2 \ (S1 + m) .
If |I| ≥ (h0 /8) · |S| then there will be at least d 0 · |I| ≥ (h0 /16) · d · |S| edges of the form x 7→ x − m from
S2 to the outside of S1 and so we are done.
We now deal with the case when |I| < (h0 /8) · |S|. In this case we must have
1 h0
|S1 | ≥ − · |S| ,
2 8
for otherwise |I| can be bounded from below by |S2 | − |S1 | > (h0 /4) · |S|. We now use the expansion of Am
to claim that there are at least h0 · d 0 · |S1 | ≥ h0 · (d/2) · (1/2 − h0 /8) · |S| edges from S1 to the complement
of S1 ∪ (S1 + m). Of these edges, at most d 0 · |I| ≤ (d/2) · (h0 /8) · |S| can land in S2 . Therefore, there are
at least
1 1 h0 h0 h0
· h0 · − − · d · |S| ≥ · d · |S|
2 2 8 8 16
edges from S to its complement in this case. This concludes the proof of the theorem.
4.2 The iterative construction
We now combine Lemma 3.1 with Theorem 4.2 to give a construction of monotone expanders with degree
close to constant. We denote by log(c) (n) the log function iterated c times.
Theorem 4.3 (Monotone expanders with degree log(c) (n)). For every c > 0 there exists a strongly explicit
family of monotone graphs Mk = (Vk , ( f1 , . . . , fdk )) such that
1. |Vk | = Θ(k),
2. dk ≤ O(log(c) (k)),
c
3. h(Mk ) ≥ Ω e−e .
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308 300
M ONOTONE E XPANDERS : C ONSTRUCTIONS AND A PPLICATIONS
Proof. We describe an algorithm for producing Mk in c iterations. We start with a graph G1 that has
degree log(k)O(1) and at each iteration decrease the degree to the logarithm of the previous degree using
the replacement product.
Set G1 to be Bk , the graph given by Theorem 4.2 on input k. Let D1 be the degree of G1 , so
D1 = log(k)O(1) . Let BD1 be given again by Theorem 4.2, this time on D1 vertices and with degree
D2 = log(D1 )O(1) . We can take the replacement product
G2 = G1 ◦ BD1 .
From Lemma 3.1 we see that G2 is a monotone graph on k · D1 vertices with degree 2D2 = (log log(k))O(1)
and
1 1 3
h(G2 ) ≥ · h(G1 )2 · h(BD1 ) ≥ ·h ,
80 80 1
where h1 > 0 is the constant given by Theorem 4.3.
We can continue in this manner c times. At the j-th iteration we are given a graph G j with degree
D j = poly(log( j) (k)) and we take its replacement product with BD j . If we denote by h j the edges
expansion at the j-th iteration we see that
1 2 j
hj ≥ h · h1 ≥ (h1 /80)3
80 j−1
and so, after c iterations we will have expansion at least Ω(exp exp(c))−1 .
Tracing the growth of the vertex set size we conclude that the size of the final graph is some explicit
function of k of the form ≈ k · poly(log(k)) · poly(log log(k)) · · · poly(log(c) (k)). We can choose a starting
integer k0 , slightly smaller than k, so that the final graph will have size Θ(k).
The part of the theorem claiming strong explicitness can be easily verified by induction on the number
of iterations (since the base graph is strongly explicit).
From this last proof we see that, if we had an existence proof for constant-degree monotone expanders,
we could transform it into an explicit construction in the following manner: start with two iterations of
the replacement products as we did above, then, do an exhaustive search for a constant-degree monotone
expander on poly(log log(n)) vertices (this can be done in poly(n) time) and use it in the last replacement
product. This approach (introduced in [2] to give a simple explicit construction of expander graphs) can
be summarized in the next corollary.
Corollary 4.4. If there exist constant-degree monotone expanders then they can be constructed in a
strongly-explicit way.
Notice that the only reason this last corollary is of any interest is that it does not rely on Bourgain’s
proof (which shows independently that there is an explicit construction). We hope that a simple existence
proof can be found and used in conjunction with this corollary to give a simple explicit construction.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308 301
Z EEV DVIR AND AVI W IGDERSON
5 Connection to multi-pushdown graphs
In this section we deal with both monotone ordered directed graphs (as defined in Section 2) and with
undirected graphs (in the usual sense). Our goal is to show that the existence of degree-d monotone
expanders imply the existence of expanders that are d-pushdown graphs. We start by giving a formal
definition of these graphs, which are a special case of d-page graphs. For more on this interesting family
of graphs and its applications see [5, 10].
Definition 5.1 (d-page graphs). A 1-page graph is an undirected graph with ordered vertex set V = [n]
such that for every pair of edges (a, b), (c, d) ∈ [n]2 in the graph, we have that c ∈ [a, b] iff d ∈ [a, b]. In
other words, if we write down the vertices in a vertical ordered line, we could draw all the edges on the
right side of this line without having intersections between edges. A d-page graph is a union of at most d
1-page graphs on the same set of vertices under the same ordering.
A d-pushdown graph is a d-page graph such that in each page the degree of each vertex is at most one.
It is easy to see where these graphs get their name from—they describe a sequence of insertions/deletions
from d pushdown stacks (“first in last out”).
Definition 5.2 (d-pushdown graphs). A 1-pushdown graph is a 1-page graph in which the degree of each
vertex is at most one. A d-pushdown graph is a union of at most d 1-pushdown graphs (on the same set
of vertices, under the same ordering).
The next claim shows how a monotone graph of degree d can be transformed into a d-pushdown
graph with roughly the same expansion (the vertex expansion of an undirected graph is defined in a
similar way to the directed case).
Claim 5.3. Let G = ([n], { f1 , . . . , fd }) be a monotone inverse-closed graph with f1 = id. Define H to be
an undirected graph on vertex set [2n] as follows: for every i ∈ [d] and every a ∈ [n] such that fi (a) 6= ⊥,
H contains the undirected edge (a, 2n + 1 − fi (a)). Then
1. H is a d-pushdown graph,
2. µ(H) ≥ 41 · µ(G).
Proof.
1. Each set of edges in H coming from a single fi will give us a 1-pushdown graph since two edges
(a, 2n − fi (a)) and (b, 2n − fi (b)) with a < b will satisfy a < b < 2n − fi (b) < 2n − fi (a) and so
the edges will not cross each other.
2. Let α = µ(G). Let S ⊂ [2n] be a set of vertices of size k ≤ n. We will show that S has at least
|S| · (1 + α/2) neighbors (including vertices in S). This will prove that µ(H) ≥ α/2 as was required.
We will rely on the fact that the identity mapping belongs to the graph G. Let S1 = S ∩ [n] and
S2 = S \ S1 . Let k1 = |S1 | and k2 = |S2 | so that k = k1 + k2 . Assume without loss of generality that
k1 ≥ k2 . Notice that the neighbors of S1 belong to the set [n + 1, 2n] and that the neighbors of S2
are in [n]. This means that |Γ(S)| ≥ max{2k1 , k + αk2 }, since k2 expands (it is smaller than n/2)
and k1 is copied by the identity map. If k2 ≥ k/4 then k + αk2 ≥ (1 + α/4)k and if k2 < k/4 then
2k1 ≥ (1 + α/4)k because α ≤ 1. This completes the proof.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308 302
M ONOTONE E XPANDERS : C ONSTRUCTIONS AND A PPLICATIONS
Combining Claim 5.3 with Bourgain’s construction of constant-degree monotone expanders [6] we
obtain the following corollary.
Corollary 5.4. There exist an integer d, a positive constant α, and a strongly-explicit family of n-vertex
undirected d-pushdown graphs Gn , such that µ(Gn ) ≥ α for all n.
6 Bourgain’s monotone expanders
We give here a brief outline of Bourgain’s construction of monotone expanders. Let SL2 (R) denote the
group of 2 × 2 real matrices with determinant 1. This group acts6 on the projective line P1 = R ∪ {∞} in
the following way: with each matrix
a b
A=
c d
we associate the Moebius transformation
ax + b
ψA (x) =
cx + d
(the inclusion of ∞ allows for division by zero). Furthermore, the derivative of this mapping is given by
1
ψA0 (x) =
(cx + d)2
so this is a monotone increasing function on any interval not containing −d/c.
Bourgain’s construction proceeds to find (explicitly) a finite subset of SL2 (R) (in fact, with rational
entries) that, roughly speaking, satisfies the following two conditions:
1. The matrices in the set are all close to the identity matrix and so their associated mappings do not
move any point in P1 by much.
2. They satisfy a so called “restricted spectral gap” property. This property ensures that applying their
associated maps to “nice” subsets in P1 will expand their measure by a bounded factor.
Combining these two properties and limiting our attention to a specific interval (which is possible
due to Property 1) one gets the following continuous analog of monotone expanders.
Theorem 6.1 ([6]). There exists α > 0 and an explicit finite set Ψ of smooth increasing maps ψ : [0, 1] →
[0, 1] such that for any measurable subset A of [0, 1], if |A| < 1/2 we have
max ψ(A) \ A ≥ α|A| .
ψ∈Ψ
6 A group action on a space S is a homomorphism from the group to the group of automorphisms of S.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308 303
Z EEV DVIR AND AVI W IGDERSON
The final step in the construction is to discretize it by dividing the interval [0, 1] into n intervals of
length 1/n and associating with each smooth mapping a discrete mapping from [n] to [n] in a natural
way so that expansion in measure is transformed into expansion in set size. The property of “strong”
monotonicity (no collisions) is obtained by observing that, since the derivatives of the smooth mappings
ψ used in the construction are bounded from below, one does not have more than a constant number of
edges mapping to a single vertex. This allows one to “break up” each weakly monotone mapping into a
constant number of strongly monotone (partial) mappings, while preserving expansion.
7 Conclusions and open problems
This paper wishes to popularize some facts we find remarkable: explicit constant-degree expanders
exist, whose graph structure is extremely restricted: the vertices are ordered, and edges decompose into
few monotone maps, or few legal parenthesis sequences. In particular, these graphs are “nearly planar”
in a precise sense. It would be interesting to explore the limitations of the expansion of these graphs.
For example, can a constant-degree monotone graph be a lossless expander? a Ramanujan graph? a
unique-neighbor expander? (Lossless expanders are expanders of degree d with expansion factor close to
d (so that the expansion is “maximal”). Unique-neighbor expanders are expanders in which, for every set
S of vertices, there are “many” neighbors of S that have only one neighbor in S.
Consequences of these constructions include new explicit pseudorandom objects (dimension ex-
panders) as well as a better understanding of the computation graphs of various Turing machines. We
believe that more applications of these expanders will be found. Specifically, algorithms on restricted
models, especially operating with limited access to input, may be able to utilize these new expanders.
Another remarkable feature of these expanders is that while they have an explicit construction,
no known direct (and simpler) existence proof is known. Few pseudorandom structures are known
which have an explicit construction but whose existence does not follow from some application of the
probabilistic method. We find the question of providing a simple existence proof of constant-degree
monotone expanders very appealing mathematically. Here we also motivate it by showing how any such
proof (even a highly nonconstructive one) directly implies a simple, strongly explicit construction. This
reduction uses the Zig-Zag graph product adapted to monotone graphs, further revealing the generality of
this paradigm.
In a different direction, while constant-degree monotone expanders lead to constant-degree dimension
expanders via the reduction of Dvir-Shpilka [11], in some sense this construction is not very natural. A
possibly more natural construction was conjectured by Wigderson in [28], and we conclude this section
with a formal statement of it. Recall the definition of dimension expanders from the introduction.
Conjecture 7.1 ([28]). Let G be a finite group, S = {g1 , . . . , gk } a symmetric set of generators, and
assume the associated Cayley graph is an expander; for concreteness, assume the second normalized
eigenvalue of its adjacency matrix is 1/2. Let F be a field of characteristic that does not divide |G|.
Let ρ be an irreducible representation of dimension n over F. Then ρ(g1 ), . . . , ρ(gk ) : F n → F n form a
dimension expander.
We note that the paper of Lubotzky and Zelmanov [21] mentioned above constructs constant-degree
dimension expanders over fields of characteristic 0 precisely by proving the conjecture above for such
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308 304
M ONOTONE E XPANDERS : C ONSTRUCTIONS AND A PPLICATIONS
fields (and then using any group with a constant number of expanding generators and high dimensional
irreducible representations, e. g., SL2 (p)). The same paper gives purely algebraic motivations for resolving
this conjecture for finite fields.
Acknowledgements
We thank Noga Alon and Jean Bourgain for helpful conversations. We thank Dieter van Melkebeek and
Rahul Santhanam for very helpful comments on earlier drafts of this paper.
References
[1] M IKL ÓS A JTAI , H ENRYK I WANIEC , J ÁNOS KOML ÓS , J ÁNOS P INTZ , AND E NDRE S ZEMER ÉDI:
Construction of a thin set with small Fourier coefficients. Bull. Lond. Math. Soc., 22:583–590, 1990.
[doi:10.1112/blms/22.6.583] 299
[2] N OGA A LON , O DED S CHWARTZ , AND A SSAF S HAPIRA: An elementary construc-
tion of constant-degree expanders. Combin. Probab. Comput., 17(3):319–327, 2008.
[doi:10.1017/S0963548307008851] 292, 293, 297, 301
[3] N OGA A LON , PAUL S EYMOUR , AND ROBIN T HOMAS: A separator theorem for graphs with an
excluded minor and its applications. In Proc. 22nd STOC, pp. 293–299, New York, NY, USA, 1990.
ACM Press. [doi:10.1145/100216.100254] 292
[4] B OAZ BARAK , RUSSELL I MPAGLIAZZO , A MIR S HPILKA , AND AVI W IGDERSON: Definition and
existence of dimension expanders, 2004. Discussion (no written record). 293
[5] F RANK B ERNHART AND PAUL C. K AINEN: The book thickness of a graph. J. Combin. Theory Ser.
B, 27(3):320–331, 1979. [doi:10.1016/0095-8956(79)90021-2] 302
[6] J EAN B OURGAIN: Expanders and dimensional expansion. C. R. Math., 347(7–8):357–362, 2009.
[doi:10.1016/j.crma.2009.02.009] 293, 303
[7] J EAN B OURGAIN AND A LEX G AMBURD: On the spectral gap for finitely-generated subgroups of
SU(2). Invent. Math., 171:83–121, sep 2007. [doi:10.1007/s00222-007-0072-z] 293
[8] E MMANUEL B REUILLARD: A strong Tits alternative. Technical Report arXiv:0804.1395, ArXiv
e-print repository, April 2008. [arXiv:0804.1395v1] 293
[9] J ONATHAN F. B USS AND P ETER W. S HOR: On the pagenumber of planar graphs. In Proc. 16th
STOC, pp. 98–100, New York, NY, USA, 1984. ACM Press. [doi:10.1145/800057.808670] 294
[10] FAN R. K. C HUNG , F RANK T HOMSON L EIGHTON , AND A RNOLD L. ROSENBERG: Embedding
graphs in books: A layout problem with applications to VLSI design. SIAM J. Algebr. Discrete
Methods, 8(1):33–58, 1987. [doi:10.1137/0608002] 302
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308 305
Z EEV DVIR AND AVI W IGDERSON
[11] Z EEV DVIR AND A MIR S HPILKA: Towards dimension expanders over finite fields. In Proc. IEEE
23rd Ann. Conf. Comput. Complex. (CCC), pp. 304–310, Washington, DC, USA, 2008. IEEE Comp.
Soc. Press. [doi:10.1109/CCC.2008.19] 293, 294, 299, 304
[12] Z VI G ALIL , R AVI K ANNAN , AND E NDRE S ZEMER ÉDI: On nontrivial separators for k-page graphs
and simulations by nondeterministic one-tape Turing machines. In Proc. 18th STOC, pp. 39–49,
New York, NY, USA, 1986. ACM Press. [doi:10.1145/12130.12135] 292, 295
[13] A RAM H ARROW: Quantum expanders from any classical Cayley graph expander. Quantum Inf.
Comput., 8(8/9):715–721, 2008. QIC Volume 8. 293
[14] S HLOMO H OORY, NATHAN L INIAL , AND AVI W IGDERSON: Expander graphs and their applica-
tions. Bull. Amer. Math. Soc. (N.S.), 43:439–561, 2006. [doi:10.1090/S0273-0979-06-01126-8]
292
[15] M ARTIN K ASSABOV, A LEXANDER L UBOTZKY, AND N IKOLAY N IKOLOV: Finite simple groups as
expanders. Proc. Natl. Acad. Sci. USA, 103(16):6116–6119, 2006. [doi:10.1073/pnas.0510337103]
292
[16] M ARIA M. K LAWE: Limitations on explicit constructions of expanding graphs. SIAM J. Comput.,
13(1):156–166, 1984. [doi:10.1137/0213011] 292
[17] R ICHARD J. L IPTON AND ROBERT E. TARJAN: A separator theorem for planar graphs. SIAM J.
Appl. Math., 36(2):177–189, 1979. [doi:10.1137/0136016] 295
[18] R ICHARD J. L IPTON AND ROBERT E. TARJAN: Applications of a planar separator theorem. SIAM
J. Comput., 9(3):615–627, 1980. [doi:10.1137/0209046] 292
[19] A LEXANDER L UBOTZKY, R ALPH P HILLIPS , AND P ETER S ARNAK: Ramanujan graphs. Combina-
torica, 8(3):261–277, 1988. [doi:10.1007/BF02126799] 292
[20] A LEXANDER L UBOTZKY AND B ENJAMIN W EISS: Groups and expanders. In Expanding graphs
(Princeton, NJ, 1992), DIMACS Ser. 10, pp. 95–109, Providence, RI, 1993. AMS. 292
[21] A LEXANDER L UBOTZKY AND E FIM Z ELMANOV: Dimension expanders. J. Algebra, 319(2):730–
738, 2008. [doi:10.1016/j.jalgebra.2005.12.033] 293, 304
[22] G. A. M ARGULIS: Explicit group-theoretic constructions of combinatorial schemes and their
applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii,
24(1):51–60, 1988. 292
[23] W OLFGANG J. PAUL , N ICHOLAS P IPPENGER , E NDRE S ZEMER ÉDI , AND W ILLIAM T. T ROT-
TER : On determinism versus non-determinism and related problems. In Proc. 24th Ann. Symp.
Found. Comput. Sci. (SFCS), pp. 429–438, Washington, DC, USA, 1983. IEEE Comp. Soc. Press.
[doi:10.1109/SFCS.1983.39] 294, 295
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308 306
M ONOTONE E XPANDERS : C ONSTRUCTIONS AND A PPLICATIONS
[24] N ICHOLAS P IPPENGER: Advances in pebbling (preliminary version). In Proc. 9th Col-
loq. Autom. Lang. Program. (ICALP), pp. 407–417, London, UK, 1982. Springer-Verlag.
[doi:10.1007/BFb0012787] 294, 295
[25] A LEXANDER R AZBOROV, E NDRE S ZEMER ÉDI , AND AVI W IGDERSON: Constructing small
sets that are uniform in arithmetic progressions. Combin. Probab. Comput., 2:513–518, 1993.
[doi:10.1017/S0963548300000870] 299
[26] O MER R EINGOLD , S ALIL VADHAN , AND AVI W IGDERSON: Entropy waves, the zig-zag
graph product, and new constant-degree expanders. Ann. of Math., 155(1):157–187, 2002. [JS-
TOR:3062153] 292, 293
[27] R AHUL S ANTHANAM: On separators, segregators and time versus space. In Proc. IEEE 16th Ann.
Conf. Comput. Complex. (CCC), pp. 286–294, Washington, DC, USA, 2001. IEEE Comp. Soc.
Press. [doi:10.1109/CCC.2001.933895] 292, 295
[28] AVI W IGDERSON: Expanders: Old and new applications and problems. (A lecture at IPAM, UCLA),
February 2004. 304
[29] AVI W IGDERSON AND DAVID X IAO: Derandomizing the Ahlswede-Winter matrix-valued Chernoff
bound using pessimistic estimators, and applications. Theory of Computing, 4(1):53–76, 2008.
[doi:10.4086/toc.2008.v004a003] 299
AUTHORS
Zeev Dvir
Postdoc
School of Mathematics
Institute for Advanced Study, Princeton
dvir ias edu
http://www.math.ias.edu/~dvir
Avi Wigderson
Professor
School of Mathematics
Institute for Advanced Study, Princeton
avi ias edu
http://www.math.ias.edu/~avi
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308 307
Z EEV DVIR AND AVI W IGDERSON
ABOUT THE AUTHORS
Z EEV DVIR is currently a postdoc in the school of mathematics at the IAS in Princeton NJ.
He got his Ph. D. from the Weizmann Institute in Israel in 2008. His advisors were Ran
Raz and Amir Shpilka. He is interested mainly in questions in computational complexity
that have a connection with pure mathematics. He likes to play the guitar and do yoga.
AVI W IGDERSON was born in Haifa, Israel in 1956, and received his Ph. D. in 1983 at
Princeton University under Dick Lipton. He enjoys and is fascinated with studying the
power and limits of efficient computation, and the remarkable impact of this field on
understanding our world. Avi’s other major source of fascination and joy are his three
kids, Eyal, Einat, and Yuval.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 291–308 308