Eigenvalues and expansion of regular graphs.
The spectral method is the best currently known technique to prove lower bounds on expansion. Ramanujan graphs, which have asymptotically optimal second eigenvalue, are the best-known explicit expanders. The spectral method yielded a lower bound of k/4 on the expansion of linear-sized subsets of k-regular Ramanujan graphs. We improve the lower bound on the expansion of Ramanujan graphs to approximately k/2. Moreover, we construct a family of k-regular graphs with asymptotically optimal second eigenvalue and linear expansion equal to k/2. This shows that k/2 is the best bound one can obtain using the second eigenvalue method. We also show an upper bound of roughly     1+k-1  on the average degree of linear-sized induced subgraphs of Ramanujan graphs. This compares positively with the classical bound   2k-1 . As a byproduct, we obtain improved results on random walks on expanders and construct selection networks (respectively, extrovert graphs) of smaller size (respectively, degree) than was previously known.
Introduction
Expander graphs are widely used in Theoretical Computer Science, in areas ranging from parallel
computation [1, 7, 21, 28, 34] to complexity theory and cryptography [2, 8, 16, 35]. Given an
XEROX Palo Alto Research Center, 3333 Coyote Hill Road, CA 94304. This work was done mostly
when the author was at the Massachusetts Institute of Technology, and partly at DIMACS. This work
was partially supported by the Defense Advanced Research Projects Agency under Contracts N00014-92-J-
1799 and N00014-91-J-1698, the Air Force under Contract F49620-92-J-0125, and the Army under Contract
DAAL-03-86-K-0171. This paper was based on "Better Expansion for Ramanujan graphs", by Nabil Kahale,
which appeared in the 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto
Rico, October 1-4, 1991; pp. 398-404. c
flIEEE, and on "On the Second Eigenvalue and Linear Expansion
of Regular Graphs", by Nabil Kahale, which appeared in the 33rd Annual Symposium on Foundations of
Computer Science, Pittsburgh, Pennsylvania, October 24-27, 1992; pp. 296-303. c
flIEEE. An updated
version of the second paper appeared in DIMACS Series in Discrete Mathematics and Theoretical Computer
Science, Volume 10, 1993; pp. 49-62. c
flAmerican Mathematical Society.
undirected k-regular graph E) and a subset X of V , the expansion of X is defined to be the
ratio jN (X)j=jXj, where is the set of neighbors of X. An
n)-expander is a k-regular graph on n nodes such that every subset of size at most ffn has
expansion at least fi.
It is known that random regular graphs are good expanders. In particular, for any fi
there exists a constant ff such that, with high probability, all the subsets of a random k-regular
graph of size at most ffn have expansion at least fi. The explicit construction of expander graphs is
much more difficult, however. The first explicit construction of an infinite family of expanders was
discovered by Margulis [25] in 1973, and improved in [15, 5, 17].
The best currently known method to calculate lower bounds on the expansion in polynomial time
relies on analyzing the second eigenvalue of the graph. Since the adjacency matrix A is symmetric,
all its eigenvalues are real and will be denoted by -
proved that for any subset X of V ,
Therefore, in order to get high expansion, we need - to be as small as possible. However, for any
sequence G n;k of k-regular graphs on n vertices, lim inf -(G n;k
goes to infinity [3,
23, 27]. Therefore, the best expansion coefficient we can obtain by applying Tanner's result is
approximately k=4. This bound is achieved by Ramanujan graphs, which have been explicitly
constructed [23, 26] for many pairs (k; n). By definition, a Ramanujan graph is a connected k-regular
graph whose eigenvalues 6= \Sigmak are at most 2
absolute value. The relationship between
the eigenvalues of the adjacency matrix and the expansion coefficient has also been investigated
in [3, 5, 6, 12], but the bound they get, when applied to non-bipartite Ramanujan graphs and for
sufficiently large k, is no better than Tanner's bound. Other results about expanders are contained
in [9, 22, 30].
Some applications, such as the construction of non-blocking networks in [7], required an expansion
greater than k=2 for linear-sized subsets. Indeed, if the expansion of a subset X is greater than
k=2, a constant fraction its nodes have unique neighbors, i.e. neighbors adjacent to only one node
in X. This allows the construction of a matching between X and N (X) in a logarithmic number of
steps and using only local computations. Recently, Pippenger [29] showed that weak expanders are
sufficient in applications where an expansion greater than k=2 was required.
We define the linear expansion of a family of graphs Gn on n vertices to be the best lower bound
on the expansion of subsets of size up to ffn, where ff is an arbitrary small positive constant, that is
sup
jN (X)j
where X ranges over the subsets of Gn of size at most ffn. We show that if (Gn ) is a family of
k-regular graphs whose second largest eigenvalue is upper bounded by ~ -, the linear expansion of
(Gn ) is at least (k=2)
. In particular, the expansion of linear-sized subsets
of Ramanujan graphs is lower bounded by a factor arbitrary close to k=2. On the other hand, for any
integer k such that k \Gamma 1 is a prime congruent to 1 modulo 4, and for any function m of n such that
explicitly construct an infinite family of k-regular graphs Gn on n vertices such that
contains a subset of size 2m with expansion k=2. Since such a
family has asymptotically optimal second eigenvalue, this shows that k=2 is essentially the best lower
bound on the linear expansion one can obtain by the second eigenvalue method. The techniques
used in this construction can be applied to prove tightness of relationships between eigenvalues and
diameter [20]. Our results provide an efficient way to test that the expansion of linear sized subsets
of random graphs is at least k=2 \Gamma O(k 3=4 log 1=2 k). We also show that the average degree of
the induced subgraphs on linear-sized subsets of a k-regular graph G is upper bounded by a factor
arbitrary close to 1
~
1). This bound is equal to
in the case of Ramanujan graphs, improving upon the previously known bound [4] ofp
Sections 3-5 contain our main results. In Section 6, we apply our techniques to obtain improved
results on random walks on expanders. Random walks are often used in complexity theory and
cryptography, and our bound improves upon previous results in [2, 16]. Applications to selection
networks and extrovert graphs are described in Section 7. We conclude with some remarks in
Section 8.
Some of the results in this paper have appeared in an extended abstract form in [18, 19], and in
a more detalied form in [20].
Notation, definitions, and background
Throughout the paper, E) will denote an undirected graph on a set V of vertices. Let L 2 (V )
denote the set of real valued functions on V and L 2
0g. As usual,
we define the scalar product of two vectors f and g of L 2 (V ) by
and the euclidean norm of a vector f by jjf
We denote the adjacency matrix of G by
AG , or simply by A if there is no risk of confusion. The matrix A is the 0-1 n \Theta n matrix whose
entry is equal to 1 if and only (i; It defines a linear operator in L 2 (V ) that maps every
vector to the vector Af defined by
(v;w)2E
This operator is selfadjoint since 8f; g 2 L 2 (V ),
(v;w)2E
For any matrix or operator M with real eigenvalues, we denote by - i (M ) the i-th largest eigenvalue
of by -(G). For any subset W of V , we denote by
-W the characteristic vector of We denote the adjacency
matrix of the graph induced on W by AW , the real number - i (AW ) by - i (W ), and the set of nodes
at distance at most l from W by B l (W ). For the rest of this section, we assume that G is k-regular.
Fact 1 [24, 32] If B is a selfadjoint operator in a vector space L, then
Clearly, the vector - V is an eigenvector of A with eigenvalue k. The vector space L 2
invariant under A, and the eigenvalues of the restriction of A to L 2
Therefore,
Fact 2 For any g 2 L 2(V ), we have g \Delta Ag - 1 (G)jjgjj 2 .
For two column vectors g and h, we say that every coordinate of g is at most its
corresponding coordinate in h.
Fact 3 [31, page 28, ex. 1.12] If a real symmetric matrix has only nonnegative entries, its largest
eigenvalue is nonnegative and has a corresponding eigenvector with nonnegative components. This
eigenvalue is largest in absolute value.
Fact 4 If a real symmetric matrix B has only nonnegative entries, and s is a vector with positive
components such that Bs - fls, then the largest eigenvalue of B is at most fl. This property still
holds if only the off-diagonal entries of B are assumed to be nonnegative [14].
Given a graph H, the cover graph H 0 of H is the graph defined on V
is an edge if and only (u; v) 2 E and l 6= m.
Fact 5 The eigenvalues of H 0 consist of the eigenvalues of H and their negated values.
3 Main lemma
In this section, we prove the main lemma (Theorem 1) that we will use later to derive lower bounds
on the expansion.
E) is k-regular on n vertices, then for any f 2 L 2 (V ), we have
Proof We decompose f as the sum of a constant vector and a vector in L 2(V ). Let
be the orthogonal projection of f on the subspace spanned by the constant vector - V .
is the orthogonal projection of f on L 2
and so f \Delta and the Pythagorean
theorem, we have
Therefore, f \Delta Af - 1 (G)jjf We conclude the proof by noting that
=n:
Lemma 2 For any subset W of a k-regular graph G, we have - 0 (W
Proof Let g be any element of L 2 (W ). Consider the vector f 2 L 2 (V ) that coincides with g on
is null on V \Gamma W . By Eq. 3, we see that g \Delta AW . By applying Lemma 1 to
f , we have
The second equation follows from the Cauchy-Schwartz inequality. We conclude using Fact 1.
similar relation [20, Section 4.1] holds between -
already gives a restriction on the structure of induced subgraphs. For example, since the
average degree of a graph is upper bounded by its largest eigenvalue, it implies that the average
degree of the induced subgraph on W is at most - 1 which is roughly - 1 (G) for
small linear-sized subsets. To obtain a stronger restriction on the induced subgraph on a linear-sized
subset X, we will apply Lemma 2 to the set B l (X). We start by comparing the largest eigenvalue
of the subgraph induced on B l (X) to the matrix of a weighted graph associated with X.
Let \Delta X be the diagonal matrix indexed by the vertices of X and whose entry (v; v) is equal to
the degree of v in the subgraph induced on X. We will simply denote by \Delta X (v) the diagonal entry
The matrix M ' 0 ;l
X can be regarded as the matrix of the weighted graph that is induced on X and has
in addition a loop of weight on each node v of X.
Lemma 3 Suppose E) is k-regular. Let l be a positive integer, X a non-empty subset of
positive real number, and -
Proof Let (X). The idea behind the proof is as follows. Let f 2 L 2 (X) be an eigenvector
of M ' 0 ;l
X corresponding to its largest eigenvalue. We will extend f to W so that it becomes roughly
an eigenvector of AW . If the largest eigenvalue of M ' 0 ;l
were too big, we would get a large eigenvalue
for AW , contradicting the fact that - 0 (W
We define the sequence r i as follows:
The sequence r i is strictly positive and decreasing for
By Fact 3, we can assume that all the entries of f are nonnegative. We extend the vector f to W
by setting
(f(u)r d(v;u) );
denote the distance in G between v and u. Note that f is nonnegative
on W since every node in W is at distance at most l from some node in X.
Proof Let u 2 X be such that . Note that can be assumed to be at
most l since r j - 0 for be the first node on a shortest path from v to u. Since the
distance between v 1 and u is
We now distinguish two cases:
ffl Case 1. Combining Eqs. 6 and 5, we get in this case
as required.
ffl Case 2. l. In this case, the k neighbors of v are at distance at most i l from u. By
monotonicity of the sequence r, it follows that the value of f on each of these neighbors is at
least f(u)r i+1 . Using again Eq. 6, we have
Proof For any v 2 X, the value of f on each of the neighbors of v in W \Gamma X is at
least f(v)r(1). Therefore,
by Fact 1. Assume for contradiction that
this implies that (AW f) leading to a
contradiction.
For
The matrix M '
X can be regarded as the matrix of the weighted graph that is induced on X and has
in addition a loop of weight on each node v of X.
Theorem 1 Suppose E) is k-regular, and let ~
non-empty subset X of V of size at most k \Gamma1=ffl jV j, we have
where the constant behind the O is a small absolute constant.
Proof Let l = b1=2fflc and let W be the set of nodes at distance at most l from X. A simple
calculation shows that jW j - 3k l jXj - 3k \Gamma1=(2ffl) n. It follows from Lemma 2 that - 0 (W
straightforward calculation shows that
We will use the following inequalities
to show that the matrix M ' 0 ;l
X is approximated by M '
X .
Proof This follows immediately from Taylor's expansion formula.
l
Proof Since sinh((l
It follows from Claim 3 that ' O(ffl). On the other hand, Claim 4 implies that
Therefore, all entries of the diagonal matrix M '
are O(
its largest eigenvalue
is O(
1ffl). But, as a consequence of Fact 1, the function that associates to a symmetric matrix
its largest eigenvalue is subadditive. Therefore,
where the second inequality follows from Lemma 3.
Remark 1 The only place where we used in the proof the fact that - 1 (G) is the second eigenvalue
of G was in conjunction with Lemma 2 to upper bound - 0 (W ). In particular, if -   is a real number
such that for any subset W of V , we have - 0 (W Theorem 1 remains valid
replaced by -   .
Lower bounds on the expansion and on the average degree
We will derive lower bounds on the expansion by applying Theorem 1 to the union of X and N (X),
after reducing to the case where the graph is bipartite and X is on one side of the partition. The
idea is that if the expansion of X is small, a node in N (X) will be adjacent to many nodes in X, in
average. This implies that the largest eigenvalue of the weighted matrix associated to the subgraph
induced on X [ N (X) is large, contradicting with Theorem 1. We also use Theorem 1 to derive
upper bounds on the average degree of induced subgraphs.
jN (X)j
k/
r
~
where the constant behind the O is a small absolute constant.
Proof We first show how to reduce the problem to the case where the graph G is bipartite and X
is on one side of the partition. Consider the cover graph G 0 of G, as defined in Section 3. We show
that Remark 1 applies to the graph G 0 and -  be a subset of V 0 , W
the set of nodes u of V such that (u; 1g. Since the largest
eigenvalue of a graph is no less than the largest eigenvalue of any induced subgraph [10, page 156],
remind the reader that - 0 (W is the largest eigenvalue of
the subgraph of G 0 induced on W (resp. W   ), and - 0 (W p ) is the largest eigenvalue of the subgraph
of G induced on W p .) On the other hand, it follows from Fact 5 and Fact 3 that - 0 (W
Using Lemma 2, we get
as required by Remark 1. Note that we cannot apply directly Theorem 1 because, by Fact 5, we
have which may be different from - 1 (G).
Let Y be the subset of V 0 equal to X \Theta f0g. Denote the adjacency matrix of G 0 by A 0 , and the
set of neighbors of Y in G 0 by N 0 (Y ). Let ~
applying Remark 1
to the graph G 0 , the set of vertices Y [ we see that the largest eigenvalue of
the matrix M
is at most ~ -(1 O(ffl)). Now, consider the function f 2 L
defined
The left-hand side is the sum of two terms. The first is equal to A 0 f \Delta f , and the second corresponds
to the weighted self-loops. By Eq. 3, we have A j. On the other hand, since the
loops have no weight on Y and have average weight e \Gamma'
the second term is equal to e \Gamma'
reduces to
By replacing jY j by jXj, jN 0 (Y )j by jN (X)j, we get after simplifications
Noting that ~ -
jN (X)j
We conclude the proof using the formulae ' cosh '
r
r
subset X of V of size at most k \Gamma1=ffl jV j, the average degree oe of the subgraph of G induced on X is
at most '
~ -+
s
~
where the constant behind the O is a small absolute constant.
Proof We use the same notations as in Theorem 1. As noted before, the matrix M '
X can be
regarded as the matrix of the weighted graph on X that is induced on X and has in addition a loop
of weight on each node v of X. By Fact 1, we have -X \Delta M '
X )jXj, which translates into
This implies
We conclude by noting that e
5 A family of almost Ramanujan graphs with expansion k=2
In this section, we construct explicity a family of k-regular graphs Gn containing subsets of sublinear
size having expansion k=2, and such that -(Gn
1. For this, we need the following
lemma.
Lemma 4 Consider a graph on a vertex set W , a subset X of W , a positive integer h, and s 2
be the set of nodes at distance i from X. Assume the following conditions hold:
1. For h, all nodes in X i have the same number of neighbors in X j .
2. The vector s is constant on X h\Gamma1 and on X h .
3. s has positive components and As -s on B h\Gamma1 (X), where - is a positive real number.
Then for any g 2 L 2 (W ) such that (X), we have
Proof Let h be the projections on the sets B
We need to show that jjP h gjj 2 =jjP h sjj 2 - jjP
operator A h corresponds in some sense to the adjacency matrix of the subgraph induced on B h (X),
but it acts on L 2 (W ). By the conditions of the lemma, there exist positive coefficients ff, fi and fl
such that P h A h By hypothesis, we have A h s -P s
Premultiplying both sides of this equation by P and A h yields successively
s:
But the matrix A h PA has only nonnegative entries off its diagonal,
and so its largest eigenvalue is 0 since s is positive (Fact 4.) The quadratic form associated to this
matrix is therefore negative semi-definite (Fact 1), and so
Since both A h and P are selfadjoint and since P the left-hand side of Eq. 9 is equal to
jjP A h gjj 2 . We can rewrite Eq. 9 as follows:
But jjP A h by hypothesis, and so
On the other hand, since A h and P h are selfadjoint, we have A h P h s
fijjP . Comparing this with Eq. 10 concludes the proof.
Theorem 4 For any integer k such that k \Gamma 1 is prime, we can explicitly construct an infinite
family of k-regular graphs Gn on n vertices whose linear expansion is k=2 and such that - 1 (Gn ) -p
n).
Proof We construct the family (Gn ) by altering the known constructions of explicit Ramanujan
graphs, so that the expansion of (Gn ) is k=2. From [23] and [26], we know that we can explicitly
construct an infinite family of bipartite Ramanujan graphs (Fn ) on n vertices whose girth c(Fn )
E) be an element of the family, u 2 V a vertex of Fn and
2. Let u be the neighbors of u and let v vertices at distance
two from u such that The subgraph of Fn induced on B l+1 (fug) is a tree since it
contains no cycles. Let u 0 and v 0 be two elements not belonging to V . Consider the k-regular graph
Fig. 1 shows the graph Gn+2 in the neighborhood of u in the case
For shorthand, we denote AFn by A, AGn+2 by A 0 and - 1 We need to show that - 0 -
(otherwise we are done), and let -
with
be an eigenvector corresponding to - 0 .
We outline informally the basic ideas of the proof. Roughly speaking, we will show that the
values that g takes on the nodes u are small compared to jjgjj. This implies that g is close
in l 2 -norm to its restriction f on V . Lemma 1 then implies that f \Delta Af - (2+o(1))
since are small, the scalar product f \Delta Af is close to g \Delta A 0
and so - 0 -
v'

Figure

1: The graph G n+2 in the neighborhood of u in the case 3. The dotted edges
are those belonging to
Since u and u 0 have the same neighbors in Gn+2 and - 0 6= 0, we have
we have
We upper bound \Gamma2g(u i On the other hand, the equality
implies that
similar relation holds for v 0 . Combining this with Eq. 11, we get
We use Lemma 1 to bound the term f \Delta Af . Note that
and so
for sufficiently large n. Combining this with Eq. 12 and noting that 1+2k=- 0 - 4
We now compare g(u i ) and g(v i ) to jjgjj. Let s be the function on V 0 defined by
and, for at distance i from u, calculation
shows that the function s verifies the conditions of Lemma 4 for the graph G 0 , with
integer h between 1 and l + 1. Hence
Similarly,
. Combining this with Eq. 13, we get
Solving Eq. 14 yields ' 0 - (log l)=l for sufficiently large n, and so
log 2 log n
log 2
Theorem 2 implies that the linear expansion of the family (Gn ) is at least k=2. Since the subset
fu; u 0 g has k neighbors, this bound is tight.
prime congruent to 1 modulo 4, we know from [23] that there exists an infinite family of
non-bipartite k-regular Ramanujan graphs with girth at least (2=3+o(1)) log k\Gamma1 n. By repeating the
construction in Theorem 4, we obtain k-regular graphs whose second largest eigenvalue in absolute
value is
linear expansion k=2. Moreover, by adjoining nodes at regions of the
graph at sufficiently large distance from each other, we can construct for any
a family of k-regular graphs whose second largest eigenvalue in absolute value is
and containing a subset of size 2m with expansion k=2. This can be shown by a proof similar to
Theorem 4.
6 Random walks
We show that the probability that a walk stays inside a given set has an exponential decay in the
length of the walk. Our bound improves upon previous results in [2, 16], and is shown to be optimal
for many values of the parameters.
Corollary 1 If E) is k-regular and W a subset of V , the fraction of walks in G of length l
whose all vertices belong to W is at most - (ff
Proof The number of walks of length l in W is equal to the sum of entries of AW l , and so
the fraction of walks of length l in W is equal to ((AW ) l -W \Delta -W )=(k l n). On the other hand, since
is the largest eigenvalue of AW in absolute value, the largest eigenvalue of AW l is (- 0 (AW
Using Lemma 2 and Fact 1, we conclude that
as desired.
Define the density of a subset of vertices to be the ratio of its size to the total number of
vertices. Corollary 1 is optimal in the following sense: for any rational ff 2 [1=2; 1] and any rational
there exists an arbitrary large k-regular graph G and a subset W of G of density -
such that - 1 integer l, the fraction of walks in W of length l is equal to
b is the graph on
. The graph
G is regular of degree a its eigenvalues are a
-bg. The set W has density - in V , and the fraction of walks in
W of length l is -(a l , which is equal to the value given by Corollary 1.
7 Other applications
We list three applications of Theorems 2, 3.
1. Random regular graphs. It was shown in [13] that, if k is even, then for a random k-regular
graphs G, we have
probability. Using Theorem 2, we
deduce that for a random regular graph, we can prove with high probability in polynomial
time that linear sized subsets (of density at most k \Gamma1=ffl , where have expansion at
least
k/
s
2. Selection networks. We can use Theorem 2 to build explicit selection networks of small
size. A selection network is a network of comparators that classifies a set of n numbers,
where n is even, into two subsets of n=2 numbers such that any element in the first subset
is smaller than any element in the second subset. In [28], a probabilistic construction of a
selection network is given using an asymptotic upper bound of 2n log 2 n comparators. Also,
an upper bound slightly less than 6n log 2 n is shown by a deterministic construction. Using
Theorem 2, we can construct selection networks of asymptotic size (3 + o(1))n log 2 n. Indeed,
it is shown in [28] how to construct selection networks of size (2+o(1))n log 2 n from expanders
of degree 4 having linear expansion at least 3. The construction can be easily generalized to
build selection networks of size k(1=2 + o(1))n log 2 n from expanders of degree k having linear
expansion at least 3. Theorem 2 then shows that we can build explicit selection networks of
using 6-regular Ramanujan graphs.
3. Extrovert graphs. Given a graph E) and a subset X of V , an element of X is
said to be extrovert if at least half of its neighbors are outside X. A family of graphs is
called extrovert if all linear-sized subsets contain a constant fraction of extrovert nodes. Such
graphs have been used [11] to solve the token distribution problem. Theorem 3 shows that
the average degree of the nodes of a linear-sized induced subgraph of a k-regular Ramanujan
graph is upper bounded by roughly 1
which is less than k=2 for k - 7. This shows
that Ramanujan graphs of degree at least 7 are extrovert graphs. Classical results [4] require
the degree to be at least 15.
Concluding remarks and further work
1. Let H be a graph of maximum degree at most k, and - a real number no smaller than 2
Theorem 1 implies that, if there exists an infinite family Gn of k-regular graphs containing H
as an induced subgraph and such that -(Gn
H can be
defined similarly to M '
prime congruent to 1 modulo 4, this condition can be
shown to be sufficient [20].
2. It is still an open question whether there exists a family of Ramanujan graphs with linear
expansion at most k=2.
3. It would be interesting to calculate the exact value of the linear expansion of the known explicit
constructions of Ramanujan graphs [23, 26]. Theorem 2 shows that it is at least k=2. On the
other hand, an easy combinatorial argument shows that the linear expansion of any family of
k-regular graphs is at most k \Gamma 1. Besides being Ramanujan, the graphs constructed in [23, 26]
have other interesting combinatorial properties. For example, they are Cayley graphs and have
high girth, unlike the graphs that we constructed in Section 5. This leads us to conjecture
that their linear expansion is strictly greater than k=2. Any explicit construction of k-regular
graphs with provable linear expansion strictly greater than k=2 would also be interesting.



--R

Sorting in c log n parallel steps.
Deterministic simulation in logspace.

Explicit construction of linear sized tolerant networks.
Better expanders and superconcentrators.


Randomness in interactive proofs.
Constructions of telephone networks by group representations.
Graph Theory.

Algebraic Discrete Methods
On the second eigenvalue and random walks in random regular graphs.
Some geometric aspects of graphs and their eigenfunctions.
Explicit constructions of linear sized superconcentrators.
preserving amplification of hardness.
Expanders obtained from affine transformations.
Better expansion for Ramanujan graphs.
On the second eigenvalue and linear expansion of regular graphs.
Expander Graphs.
Fast algorithms for routing around faults on multibutterflies.
Discrete groups
Ramanujan graphs.
A Survey of Matrix Theory and Matrix Inequalities.
Explicit constructions of concentrators.
Explicit group-theoretical constructions of combinatorial schemes and their applications to the design of expanders and concentrators
On the second eigenvalue of a graph.
Selection networks.

Some applications of modular forms.

Linear Algebra and its Applications.
Explicit construction of concentrators from generalized n-gons
An O(logn) deterministic packet routing scheme.
Graph theoretic properties in computational complexity.
--TR
Expanders and diffusers
Eigen values and expanders
Deterministic simulation in LOGSPACE
Better expanders and superconcentrators
Expanders obtained from affine transformations
Explicit construction of linear sized tolerant networks
Sorting in <italic>c</> log <italic>n</> parallel steps
An <i>O</i>(log<i>N</i>) deterministic packet routing scheme
On-line algorithms for path selection in a nonblocking network
Better expansion for Ramanujan graphs
Selection networks
On the second eigenvalue of a graph
Self-routing superconcentrators
Expander graphs
Near-perfect Token Distribution

--CTR
Elchanan Mossel , Sbastien Roch, Slow emergence of cooperation for win-stay lose-shift on trees, Machine Learning, v.67 n.1-2, p.7-22, May       2007
Amnon Ta-Shma , Christopher Umans , David Zuckerman, Loss-less condensers, unbalanced expanders, and extractors, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.143-152, July 2001, Hersonissos, Greece
Michael Capalbo , Omer Reingold , Salil Vadhan , Avi Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
Bruce M. Maggs , Berthold Vcking, Improved routing and sorting on multibutterflies, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.517-530, May 04-06, 1997, El Paso, Texas, United States
Robert Els , Burkhard Monien, Load balancing of unit size tokens and expansion properties of graphs, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
David Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
David Peleg, Local majorities, coalitions and monopolies in graphs: a review, Theoretical Computer Science, v.282
expander graphs;load balancing;selection networks;random walks;induced subgraphs;ramanujan graphs;eigenvalues