Construction of Expanders and Ramanujan

Graphs and Their Applications

by Selin Kalaycıoğlu

Copyright \begin{matrix}c \\ ◯ \end{matrix} Selin Kalaycıoğlu 2004

A Dissertation Submitted to the Faculty of the

Department of Mathematics

In Partial Fulfillment of the Requirements

For the Degree of

Master of Science

In the Graduate College

The University of Arizona

2 0 0 4

Get the official approval page from the Graduate College before your final defense.

Statement by Author

This dissertation has been submitted in partial fulfillment of requirements for an advanced degree at The University of Arizona and is deposited in the University Library to be made available to borrowers under rules of the Library.

Brief quotations from this dissertation are allowable without special permission, provided that accurate acknowledgment of source is made. Requests for permission for extended quotation from or reproduction of this manuscript in whole or in part may be granted by the copyright holder.

Signed:

Approval by Dissertation Director

This dissertation has been approved on the date shown below:

Dinesh Thakur Professor of Mathematics Date

Table of Contents

List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.1. Rephrasing the main problem using graph theory . . . . . . . . 8 2. Existence of the (n, k, c) Expanders . . . . . . . . . . . . . . . . . . 12 3. Ramanujan Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.1. Rephrasing the main problem using eigenvalues . . . . . . . . . 25 4. Construction of X^{p,q} . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.1. Background on integral quaternions: H(Z) . . . . . . . . . . . . 33 4.2. Properties of X^{p,q} . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.3. The graph Y^{p,q} and its connection with X^{p,q} . . . . . . . . . . . 38

5. Zig-Zag Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.2. The construction and the proof of the zig-zag theorem . . . . . 57

6. Applications of Expanders . . . . . . . . . . . . . . . . . . . . . . . 68 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

List of Figures

Figure 1.1. Complete graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Figure 1.2. Finding the boundary, ∂F . . . . . . . . . . . . . . . . . . . . . 9 Figure 1.3. Minimally connected 2-regular graph . . . . . . . . . . . . . . . 10

Figure 5.1. [3, 2, 1/2]-expander . . . . . . . . . . . . . . . . . . . . . . . . . 54 Figure 5.2. [3, 4, 1/4]-expander . . . . . . . . . . . . . . . . . . . . . . . . . 55 Figure 5.3. G = [3, 2, 1/2]-expander . . . . . . . . . . . . . . . . . . . . . . 58 Figure 5.4. H = [2, 2, 0]-expander . . . . . . . . . . . . . . . . . . . . . . . 58 Figure 5.5. G ⋊ H = [6, 4, 1/2]-expander . . . . . . . . . . . . . . . . . . . 59 Figure 5.6. G ⋊ H = [6, 4, 1/2]-expander . . . . . . . . . . . . . . . . . . . 61 Figure 5.7. G ⋊ H = [6, 9, 0.62284]-expander . . . . . . . . . . . . . . . . . 62

Abstract

The motivation for our problem is to construct a model for an efficient communication network. This model could be the telephone network of a country, the wiring of big parallel computers, or the neuronal system of a human body. Starting from the design of communication networks, one passes to a problem about graphs which is solved by fundamental results of number theory and group theory. These are of great interest in both pure and applied mathematics. We discuss ‘Expanders’ and ‘Ramanujan graphs’ which can be good models for an efficient communication network. In chapter 1, the relevant terminology about graph theory is given to help us formulate our real life problem in terms of graph theory. In chapter 2, a probabilistic proof of the existence of expanders is given. In chapter 3, properties of graphs and properties of the eigenvalues of their adjacency matrix are explored, and Ramanujan graphs are defined. In chapter 4, explicit constructions of Ramanujan Cayley graphs based on group theory and integral quaternions are explored and properties of these graphs are discussed. In chapter 5, a recently developed method of finding expanders, the Zig-zag product, is introduced. In chapter 6, applications of expander graphs to error-correcting codes, complexity theory and cryptography are discussed.

Construction of Expanders and Ramanujan Graphs and Their Applications

Selin Kalaycıoğlu, M.S. The University of Arizona, 2004

Director: Dinesh Thakur

The motivation for our problem is to construct a model for an efficient communication network. This model could be the telephone network of a country, the wiring of big parallel computers, or the neuronal system of a human body. Starting from the design of communication networks, one passes to a problem about graphs which is solved by fundamental results of number theory and group theory. These are of great interest in both pure and applied mathematics. We discuss ‘Expanders’ and ‘Ramanujan graphs’ which can be good models for an efficient communication network. In chapter 1, the relevant terminology about graph theory is given to help us formulate our real life problem in terms of graph theory. In chapter 2, a probabilistic proof of the existence of expanders is given. In chapter 3, properties of graphs and properties of the eigenvalues of their adjacency matrix are explored, and Ramanujan graphs are defined. In chapter 4, explicit constructions of Ramanujan Cayley graphs based on group theory and integral quaternions are explored and properties of these graphs are discussed. In chapter 5, a recently developed method of finding expanders, the Zig-zag product, is introduced. In chapter 6, applications of expander graphs to error-correcting codes, complexity theory and cryptography are discussed.

1. Overview

Suppose we want to construct efficient communication networks at a low cost. The purpose of the network is to transmit information quickly. Assume a few individuals know the information. Suppose that in one unit of time the information can be carried to all the nearest neighbors of the individuals. In the next unit of time the information is carried to the next neighbors of neighbors and so forth. How long does it take before all the individuals receive the information? The individuals wishing to communicate through the network will be represented by the vertices of a graph and the communication cables will be represented by the edges of a graph. To shorten the transmission time what we need is that every subset of vertices has a lot of distinct neighbors. For example in a complete graph where all vertices are connected to each other (see Figure 1.1), information is carried in one unit time.

Figure 1.1. Complete graph

On the other hand the total length of cables needed to wire a network is also a quantity we would like to shorten. So, if you think about our previous example with the complete graph, it is good if you just consider time, however it is not good with respect to the length of cables which cost too much.

We will study families of graphs, called expanders, which satisfy everything that we need for the efficient communication network. Many mathematicians are interested in the expander graphs since it is a really hard problem to give the explicit construction of a family of the expanders.

1.1. Rephrasing the main problem using graph theory

Let us formulate our problem in terms of graph theory. An efficient communication network is thus represented by a graph with small number of edges and such that every subset of vertices has many distinct neighbors. We will look at a graph X(V, E) where V is the set of vertices and E is the set of edges. We will assume that X is finite and undirected.

Definition. A path in X is a sequence v_{1}v_{2} … v_{k} of vertices where v_{i} is adjacent to v_{i+1}, i.e. (v_{i}, v_{i+1}) is an edge.

Definition. A graph is connected if any two vertices can be joined by a path.

Definition. A loop in a graph is an edge from a vertex to itself.

Definition. A graph is complete if any two distinct vertices are connected by an edge.

Definition. A graph is simple if it has no loops and there is at most one edge joining adjacent vertices.

Definition. A graph is bipartite if it is possible to paint the vertices of the graph in two colors, in such a way that adjacent vertices have distinct colors.

In chapter 2 we allow graphs to have multiple edges, in chapter 5 we allow graphs to have both loops and multiple edges and in chapter 3 we focus on connected and simple graphs.

Definition. A graph is k-regular if every vertex has exactly k neighbors.

For our efficient communication network families we put a bound k on the maximum number of edges through a vertex. In particular we concentrate on k-regular graphs since the combinatorics of k-regular graphs make our computations easier.

Definition. Given any subset F ⊂ V, the boundary, ∂F, is the set of edges connecting F to the complement V − F and the neighbor set of F, denoted by N(F), is the set of vertices in V − F, which are adjacent to the vertices in F.

Example:

Figure 1.2. Finding the boundary, ∂F

If F = {a, b} then ∂F = {(a, e), (a, f), (b, g), (b, c)} and N(F) = {e, f, g, c}.

Definition. The expanding constant of the graph X is

h(X) = min \{ \frac{|∂F |}{|F |} : F ⊆ V, 0 < |F | ≤ \frac{|V |}{2}\}  (1.1)

If we view X as a network transmitting information then h(X) measures the quality of X as a network. If h(X) is large then the information propagates well. Basically h(X) measures the speed at which information can be transmitted through the network represented by X.

We could use |N(F)|/|F | in place of |∂F |/|F | to give a variant of expanding constant. For k-regular graphs |∂F | ≥ |N(F)| ≥ |∂F |/k. So it does not make a difference which variant we use for our problem of getting a family with expanding constant bounded away from zero.

Example. Let us look at the expansion constant of a complete (n − 1)-regular graph (see Figure 1.1), on n vertices. Suppose |F | = l then |∂F | = l(n − l). h(X) = min \frac{l(n−l)}{l} = min(n − l) = n − ⌈\frac{n}{2}⌉ ∼ \frac{n}{2}. Hence if n → ∞ then h(X) → ∞.

Example. Now let us look at the expanding constant of a minimally connected connected 2-regular graph on n vertices. Figure 1.3 shows a minimally connected graph on 6 vertices. Suppose |F | is a half cycle. Then |∂F | = 2 and h(X) = min \frac{2}{⌈ \frac{n}{2} ⌉} ∼ \frac{4}{n}. Therefore if n → ∞ then h(X) → 0

Figure 1.3. Minimally connected 2-regular graph

Since for our optimal network we want high speed and small cost the graph we want to construct which will represent this communication network should have small k and large h(X).

Definition. We will call a k-regular graph X on n vertices satisfying h(X) ≥ c for some constant c > 0 by (n, k, c)-expander.

Definition. Let (X_{m})_{m≥1} be a family of finite, connected and k-regular graphs. Let c > 0 and k be an integer. We call this, a family of (k, c)-expanders, if |V_{m}| → ∞ for m → ∞ and h(X_{m}) ≥ c for every m ≥ 1.

Main Problem: Giving explicit constructions for families of expanders. We study in this paper two different approaches:

1. The first method uses an algebraic way to construct an expander graph as the Cayley graph of PSL_{2}(F_{q}) and PGL_{2}(F_{q}) with suitable generators.

2. The second method is a combinatorial, graph theoretic method, called the Zigzag product.

2. Existence of the (n, k, c) Expanders

Before starting to look at the different approaches of constructing expanders a natural question one might ask could be ‘Why do the expanders exist?’. The probability that a random graph is an expander is asymptotically 1. This can be shown by a probabilistic argument, see [16]. In this section we will only show that the probability for a random k-regular graph to be an (n, k, c)-expander is greater than zero and once we prove that by repeating this process we get a probability as close to 1 to get an expander from a random graph as desired.

Definition. A matching on a graph G is a set of edges of G such that no two share a vertex in common. The largest possible matching on a graph with n vertices with n even consists of n/2 edges, and such a matching is called a perfect matching.

We will make a random k-regular graph G_{n,k} for even n as follows: First of all we will list all the possible perfect matchings of n vertices with n/2 edges. Then we will choose randomly k of the perfect matchings and take their union. Hence we will get a k-regular graph with nk/2 edges. Note that G_{n,k} may have multiple edges but this is so rare that the following claim will still work. So in the proof below we assume that G_{n,k} is simple.

Claim 1. Given c < 1, there exists θ > 0 if k is large enough so that e^{2}(1 + c)(\frac{1+c}{2})^{\frac{k}{2} −1} < 1/2 then for large enough even n, randomly chosen G_{n,k} will be (n, k, c)-expander with probability greater than θ.

Proof. Let us take any subset F of the vertex set V such that |F | < |V |/2. Let N(F) denote the neighbor set of F. From the definition of the ∂F, it is clear that |∂F | ≥ |N(F)| and F ⋂ N(F) = Ø. Hence |F ⋃ N(F)| = |F | + |N(F)|. We will look at the sets F which are violating the expansion constant, i.e. |∂F | < c|F | ⇔ |∂F | + |F | < c|F | + |F | ⇒ |F ⋃ N(F)| < (1 + c)|F |. For simplicity let us denote |F | = f and |F ⋃ N(F)| = q. Let us choose an arbitrary set Q ⊃ F such that |Q| = q. For any q there are \binom{n}{q}\binom{q}{f} such (F, Q) pairs. For each such (F, Q) we will calculate an upper bound on the probability that N(F) ⋃ F ⊂ Q as a function of the size Q and then we will show that when you sum up over all the different sizes of Q the resulting probability is less than one. Since we are counting the number of pairs (F, Q) where F violates the expansion constant, i.e. q < f(1 + c), we get the following inequality:

\binom{n}{q}\binom{q}{f} ≤ (\frac{ne}{q})^{q}(\frac{qe}{f})^{f} ≤ (\frac{ne^{2}(1 + c)}{q})^{q}

For any given pair and a random perfect matching the probability that a single random matching pairs all vertices of F with vertices in Q is no more than (q/n)^{f/2}, since we have to make at least f/2 decisions for the vertices in F to pair and the probability of each decision to get paired with a vertex of Q is no more than q/n. Hence for k random perfect matches this probability is no more than (q/n)^{fk/2} ≤ (q/n)^{kq/2}, since f < q. Thus for a fixed q the probability that there is any such pair over k matchings is less than

(\frac{ne^{2}(1 + c)}{q})^{q}(\frac{q}{n})^{\frac{kq}{2}} = (e^{2}(1 + c)(\frac{q}{n})^{\frac{k}{2} −1})^{q} ≤ (e^{2}(1 + c)(\frac{1 + c}{2})^{\frac{k}{2} −1})^{q}

where we used in the last inequality the fact that q < f(1 + c) < n/2(1 + c). For any c < 1 and sufficiently large k, e^{2}(1 + c)(\frac{1+c}{2})^{\frac{k}{2} −1} is less than \frac{1}{2}, hence the sum over all q > 0 is less than 1.

3. Ramanujan Graphs

Definition. Let V = {v_{1}, v_{2}, …, v_{n}} be the set of vertices of X. Then we define the adjacency matrix of the graph X as the matrix A indexed by pairs of vertices v_{i}, v_{j} ∈ V as follows:

A has entries A_{ij} where A_{ij} is the number of edges joining v_{i} to v_{j}. From the definition it is easy to see the following:

1. X is simple ⇔ A_{ij} ∈ {0, 1} for every v_{i} and v_{j}.

2. X is undirected ⇔ A is symmetric.

3. X has no loops ⇔ A_{ii} = 0 for every v_{i} ∈ V.

4. If X is k-regular then for every v_{i} ∈ V

∑_{v_{j}∈V} A_{ij} = k.

So if X is a finite graph on n vertices then A is an n × n symmetric matrix, hence it has n real eigenvalues, counting multiplicities that we can list in decreasing order, which is called the spectrum of X.

μ_{0} ≥ μ_{1} ≥ … ≥ μ_{n−2} ≥ μ_{n−1}  (3.1)

Proposition 1. Let X be a finite k-regular graph with n vertices. Then a) μ_{0} = k;

b) |μ_{i}| ≤ k for 1 ≤ i ≤ n − 1; Proof. Since the adjacency matrix of a k-regular graph has every row sum equal to k, we clearly have that μ_{0} = k is an eigenvalue of the adjacency matrix A with eigenvector equal to (1, 1, 1, …, 1)^{T}.

Let us prove that if μ is any eigenvalue then |μ| ≤ k. Let v = (x_{1}, x_{2}, …, x_{n})^{T} be an eigenvector of A with eigenvalue μ. Without loss of generality, suppose |x_{1}| = max_{1≤i≤n} |x_{i}|. We may also suppose x_{1} > 0. Then

|μ|x_{1} = |μx_{1}| = | ∑_{1≤j≤n} a_{1j}x_{j}| ≤ ∑_{1≤j≤n} a_{1j}|x_{j}| ≤ ∑_{1≤j≤n} a_{1j}x_{1} = x_{1} ∑_{1≤j≤n} a_{1j} = kx_{1}

Canceling out x_{1} gives the result.

Definition. The largest positive eigenvalue μ_{0} = k is called the trivial eigenvalue.

Definition. The difference μ_{0} − μ_{1} = k − μ_{1} is called the spectral gap.

Proposition 2. Suppose X is simple, k-regular and connected. Then μ_{0} = k has multiplicity 1.

Proof. Let (x_{1}, x_{2}, …, x_{n})^{T} be an eigenvector associated with the eigenvalue μ_{0}. By renumbering the vertices, if necessary, we can assume that |x_{1}| = max |x_{j}| for all 1 ≤ j ≤ n. Replacing x_{1} by −x_{1}, if necessary, we may assume that x_{1} > 0. Then we get x_{1} = ∑_{j} \frac{a_{1j}}{k} x_{j}. Hence x_{1} is a linear combination of numbers which are less than x_{1}. Therefore x_{1} = x_{j} for all j such that a_{1j} = 1. If k is such that a_{1k} = 0, let v_{1}, v_{i_{2}}, …, v_{k} be a path, which exists because X is connected. By our proof we get x_{1} = x_{i_{2}} = … = x_{k} by repeating the argument. Hence all the entries of the eigenvector are equal to each other.

Proposition 3. Let X be a connected, k-regular graph on n vertices. The following are equivalent.

1. X is bipartite; 2. The spectrum of X is symmetric about 0;

3. μ_{n−1} = −k.

The proof of this proposition can be found in [6]. □

Let us look at the adjacency matrix and calculate its eigenvalues, for the two different families in section 1.1.

Example.

Claim 2. The (n − 1)-regular graph on n vertices has 2 eigenvalues: the eigenvalue −1 occurs with multiplicity n − 1 and the eigenvalue n − 1 occurs with multiplicity 1.

Proof. Suppose v is an eigenvector associated with the eigenvalue μ. Let us denote the adjacency matrix of the graph by A. Then (A − μ · I)v = 0. The dimension of the eigenspace is n − rank(A − μ · I). Since (A − μ · I) is the matrix with −μ on the diagonal and 1’s on all other entries for μ = −1 the rank of (A − μ · I) is 1. So the dimension of the eigenspace is n − 1. Hence -1 is an eigenvalue with multiplicity (n − 1). We have shown that the regularity of the graph is the trivial eigenvalue and it has multiplicity one if the graph is connected. Since our graph is (n − 1)-regular connected graph n − 1 is the trivial eigenvalue with multiplicity 1.

Example.

Claim 3. The eigenvalues of the 2-regular graph on n vertices are 2 cos \frac{2πj}{n} where 0 ≤ j ≤ (n − 1).

Proof. Without loss of generality the adjacency matrix of a 2-regular graph looks as follows:

A = ( \begin{matrix}0 & 1 & 0 & … & 0 & 1 \\ 1 & 0 & 1 & 0 & … & 0 \\ 0 & 1 & 0 & 1 & … & 0 \\ ⋮ & ⋮ & ⋮ & … & ⋮ & ⋮ \\ 0 & … & … & 1 & 0 & 1 \\ 1 & 0 & 0 & … & 1 & 0 \end{matrix} )

We can write A = T + T^{−1} where

T = ( \begin{matrix}0 & 0 & 0 & … & 0 & 1 \\ 1 & 0 & 0 & 0 & … & 0 \\ 0 & 1 & 0 & 0 & … & 0 \\ ⋮ & ⋮ & ⋮ & … & ⋮ & ⋮ \\ 0 & … & … & 1 & 0 & 0 \\ 0 & 0 & 0 & … & 1 & 0 \end{matrix} )

and

T^{−1} = ( \begin{matrix}0 & 1 & 0 & … & 0 & 0 \\ 0 & 0 & 1 & 0 & … & 0 \\ 0 & 0 & 0 & 1 & … & 0 \\ ⋮ & ⋮ & ⋮ & … & ⋮ & ⋮ \\ 0 & … & … & & 0 & 1 \\ 1 & 0 & 0 & … & 0 & 0 \end{matrix} )

T is the companion matrix for the polynomial x^{n} − 1, hence T has n different eigenvalues (e^{2πi/n})^{j} where 0 ≤ j ≤ (n − 1). Suppose v is an eigenvector associated with the eigenvalue ϵ^{j} where ϵ is the n-th root of unity. Then T v = ϵ^{j}v ⟹ T^{−1}v = ϵ^{−j}v. So T v+T^{−1}v = ϵ^{j}v+ϵ^{−j}v, so Av = (ϵ^{j} +ϵ^{−j})v. Therefore the eigenvalues are 2 cos \frac{2πj}{n} where 0 ≤ j ≤ (n − 1).

We note that when n tends to infinity, the largest nontrivial eigenvalue tends to 2, which implies that the spectral gap is tending to zero.

Theorem 1. Let X = (V, E) be a finite, connected, k-regular graph without loops. Let μ_{1} be the first nontrivial eigenvalue of X then

\frac{k − μ_{1}}{2} ≤ h(X) ≤ \sqrt{2k(k − μ_{1})}.  (3.2)

Proof. We first define the Laplace operator Δ on a finite graph without loops. Let C^{0}(X) = the space of functions on vertices of X and let C^{1}(X) = the space of functions on edges of X. For each edge e = (e^{−}, e^{+}) of X we will choose a direction, namely we will call e^{−}

the initial vertex, e^{+} the terminal vertex. Let us define the map:

d: C^{0}(X) → C^{1}(X)

by

f ↦ df

where df(e) = f(e^{+}) − f(e^{−}) for each edge e. Let us define a matrix M = (m_{v_{i}e_{j}}), where the rows of M are parameterized by the vertices of X and the columns of M are parameterized by the edges of X such that v_{i}e_{j}th entry is

1, if v = e^{+};
−1, if v = e^{−};
0, otherwise.

We identify a function f in C^{0}(X) by a row vector (f(v_{1}), f(v_{2}), …, f(v_{n})) then

df(e) = (f(v_{1}), f(v_{2}), …, f(v_{n})) · e_{j}th column of M.

Let us denote by ⟨, ⟩_{0} and ⟨, ⟩_{1} the hermitian inner product on C^{0}(X), C^{1}(X) respectively. The adjoint operator

d^{∗} = C^{1}(X) → C^{0}(X)

is given by

⟨d^{∗}g, f⟩_{0} = ⟨g, df⟩_{1}  (3.3)

for all g ∈ C_{1}(X), for all f ∈ C_{0}(X).

In terms of matrices d^{∗} is represented by \overline{M}^{T} = M^{T}.

Let us define the Laplace operator on X.

Δ = d^{∗}d: C^{0}(X) → C^{0}(X).

That is also known as the Laplace matrix Δ = D − A where D = n × n diagonal matrix (d_{ii}) where d_{ii} is the degree of i. In our case since X is k-regular D = k · I. Note that in terms of matrices Δ is represented by M^{T} · M. Hence Δ is independent of the choice of direction in each case. Let f_{0}, f_{1}, …, f_{n−1} be an orthonormal basis of C^{0}(X) consisting of the eigenvectors of A with eigenvalues μ_{0}, μ_{1}, …, μ_{n−1}. For any function f in C^{0}(X) we can write

f = ∑_{i=0}^{n−1} a_{i}f_{i}  (3.4)

Then

Δf = (D − A)f
= (k · I − A)f
= k(∑_{i=0}^{n−1} a_{i}f_{i}) − A(∑_{i=0}^{n−1} a_{i}f_{i})
= ∑_{i=0}^{n−1} a_{i}(kf_{i} − μ_{i}f_{i})
= ∑_{i=1}^{n−1} a_{i}(kf_{i} − μ_{i}f_{i}) since μ_{0} = k .

Thus

⟨df, df⟩_{1} = ⟨Δf, f⟩_{0}
= ⟨∑_{i=0}^{n−1} a_{i}(kf_{i} − μ_{i}f_{i}), ∑ a_{i}f_{i}⟩_{0}
= ∑_{i=0}^{n−1} a_{i}\overline{a_{i}}(k − μ_{i})
= ∑_{i=1}^{n−1} a_{i}\overline{a_{i}}(k − μ_{i}).

If f is perpendicular to the constant function then a_{0} = 0 and

∑_{i=1}^{n−1} a_{i}\overline{a_{i}}(k − μ_{i}) = ⟨f, f⟩_{0}.  (3.5)

Hence

⟨df, df⟩_{1} ≥ (k − μ_{1})⟨f, f⟩_{0}  (3.6)

since μ_{0} = k ≥ μ_{1} ≥ … ≥ μ_{n−1}. Now let F be a nonempty subset of the vertices with |F | ≤ \frac{|V |}{2}. Define a special function f on V by

f(x) = \{ \begin{matrix}|V − F |, & if x ∈ F; \\ −|F |, & if x ∈ V − F . \end{matrix} \}

Then ∑_{x∈V} f(x) = |F ||V − F | − |V − F ||F | = 0. Hence f is perpendicular to the constant function.

Further

df(e) = f(e^{+}) − f(e^{−}) = \{ \begin{matrix}0, & if e^{+}, e^{−} both lie in F or V − F; \\ |V |, & if e^{+} lies in F, e^{−} lies in V − F; \\ −|V |, & if e^{+} lies in V − F, e^{−} lies in F . \end{matrix} \}

⟨df, df⟩_{1} = ∑_{e∈E} df^{2}
= |V |^{2}|∂F |
≥ (k − μ_{1})⟨f, f⟩_{0}.

Note that

⟨f, f⟩_{0} = ∑_{x∈V} f(x)^{2} = |F ||V − F |^{2} + |V − F ||F |^{2} = |F ||V − F ||V |.

Therefore

|V |^{2}|∂F | ≥ (k − μ_{1})|F ||V − F ||V |

\frac{|∂F |}{|F |} ≥ (k − μ_{1})\frac{|V − F |}{|V |}.

Since |F | ≤ \frac{|V |}{2},

\frac{|∂F |}{|F |} ≥ \frac{(k − μ_{1})}{2}

Since F was arbitrary, we get

h(X) = min(\frac{|∂F |}{|F |}) ≥ \frac{k − μ_{1}}{2} ,

which proves the lower bound of the expanding constant.

Let us prove the second inequality:

h(X) ≤ \sqrt{2k(k − μ_{1})}.  (3.7)

Let f be a nonnegative-valued function on V and arrange the values of f in decreasing order.

β_{r} > … > β_{1} > β_{0} ≥ 0.  (3.8)

For each i = 0, 1, …, r define

L_{i} = {x ∈ V : f(x) ≥ β_{i}}  (3.9)

Then V = L_{0} ⊃ L_{1} ⊃ L_{2} ⊃ … ⊃ L_{r}. Now let us look at the quantity

B_{f} = ∑_{e∈E} |f(e^{+})^{2} − f(e^{−})^{2}|.  (3.10)

We can choose a direction on each edge such that f(e^{+}) ≥ f(e^{−}). Then we can write

B_{f} = ∑_{e∈E} f(e^{+})^{2} − f(e^{−})^{2}  (3.11)

Let us write f(e^{+}) = β_{i(e)}, f(e^{−}) = β_{j(e)}. Then r ≥ i(e) ≥ j(e) ≥ 0. If i(e) > j(e) then we write

β_{i(e)}^{2} − β_{j(e)}^{2} = (β_{i(e)}^{2} − β_{i(e)−1}^{2}) + (β_{i(e)−1}^{2} − β_{i(e)−2}^{2}) + … + (β_{j(e)+1}^{2} − β_{j(e)}^{2}). (3.12)

Hence

B_{f} = ∑_{e∈E} β_{i(e)}^{2} − β_{j(e)}^{2}

= ∑_{e∈E,i(e)≠j(e)}(β_{i(e)}^{2} − β_{i(e)−1}^{2}) + (β_{i(e)−1}^{2} − β_{i(e)−2}^{2}) + … + (β_{j(e)+1}^{2} − β_{j(e)}^{2})

= ∑ b_{i}(β_{i}^{2} − β_{i−1}^{2})

where b_{i} counts the number of edges e which contribute a term β_{i}^{2} − β_{i−1}^{2}, i.e. when i(e) ≥ i and j(e) ≤ i − 1, i.e. when e^{+} ∈ L_{i} and e^{−} ∈ V − L_{i}. Thus

b_{i} = |∂L_{i}|.

Hence

B_{f} = ∑_{e∈E} β_{i(e)}^{2} − β_{j(e)}^{2} = ∑_{i=1}^{r} |∂L_{i}|(β_{i}^{2} − β_{i−1}^{2})  (3.13)

We get an upper bound for B_{f} from the first expression by using the Cauchy– Schwartz inequality:

B_{f} = ∑_{e∈E}(f(e^{+}) + f(e^{−}))(f(e^{+}) − f(e^{−}))

≤ [∑_{e∈E}((f(e^{+}) + f(e^{−}))^{2})^{1/2}][∑_{e∈E}((f(e^{+}) − f(e^{−}))^{2})^{1/2}].

Since (a + b)^{2} ≤ 2(a^{2} + b^{2}) for real a, b, we get

B_{f} ≤ \sqrt{2} ∑_{e∈E}(f(e^{+})^{2} + f(e^{−})^{2})^{1/2}⟨df, df⟩_{1}^{1/2}.

From 2|E| = k|V |, it follows

B_{f} ≤ \sqrt{2}k(∑_{x∈V} f(x)^{2})^{1/2}⟨df, df⟩_{1}^{1/2}

= \sqrt{2k}⟨f, f⟩_{0}^{1/2}⟨df, df⟩_{1}^{1/2}.

Next we get a lower bound of B_{f} from 3.13 relating it to h(X). Assume that sup f = \{x ∈ V : f(x) ≠ 0\} has cardinality ≤ \frac{|V |}{2}, which implies that β_{0} = 0 and sup f = L_{1}. Therefore for i = 1, …, r, |L_{i}| ≤ |L_{1}| ≤ \frac{|V |}{2} by assumption. Hence by definition of h(X), \frac{|∂L_{i}|}{|L_{i}|} ≥ h(X), i.e. |∂L_{i}| ≥ h(X)|L_{i}| for i = 1, …, r. Thus

B_{f} = ∑ |∂L_{i}|(β_{i}^{2} − β_{i−1}^{2})
≥ ∑ h(X)|L_{i}|(β_{i}^{2} − β_{i−1}^{2})
= h(X)[|L_{r}|(β_{r}^{2} − β_{r−1}^{2}) + |L_{r−1}|(β_{r−1}^{2} − β_{r−2}^{2}) + … + |L_{2}|(β_{2}^{2} − β_{1}^{2}) + |L_{1}|(β_{1}^{2})]
= h(X)[|L_{r}|(β_{r}^{2}) + ∑_{i=1}^{r−1} |L_{i} − L_{i+1}|β_{i}^{2}].

Note that L_{i} − L_{i−1} = {x ∈ V : f(x) = β_{i}} and L_{i+1} ⊂ L_{i}. Therefore we get

B_{f} ≥ h(X)⟨f, f⟩_{0}.  (3.14)

So for any nonnegative function f on V with | sup f| ≤ \frac{|V |}{2}, we have

\sqrt{2k}⟨f, f⟩_{0}^{1/2}⟨df, df⟩_{1}^{1/2} ≥ B_{f} ≥ h(X)⟨f, f⟩_{0}.  (3.15)

Now it remains to choose an appropriate f to get an upper bound of h(X) as in the theorem. We want to relate ⟨df, df⟩_{1} to ⟨f, f⟩_{0} and involving μ_{1}.

Let g ≠ 0 be a real-valued eigenfunction of A with eigenvalue μ_{1}. Then g is perpendicular to the constant function, hence ∑_{v∈V} g(x) = 0. Then both

V^{+} = {x ∈ V : g(x) > 0}

and

V^{−} = {x ∈ V : g(x) < 0}

are nonempty and at least one of them has cardinality ≤ \frac{|V |}{2}. Replacing g by −g if necessary, we may assume |V^{+}| ≤ \frac{|V |}{2}. Let us define

f(x) = \{ \begin{matrix}g(x) & if x ∈ V^{+}; \\ 0 & otherwise. \end{matrix} \}

Then all f(x) ≥ 0 and | sup f| = |V^{+}| = \frac{|V |}{2}. We have,

Δf(x) = (k · I − A)f(x)
= kf(x) − ∑ ; y adj. to x f(y)

≤ kf(x) − ∑ ; y adj. to x g(y)
= kf(x) − Ag(x)
= kf(x) − μ_{1}g(x)
= (k − μ_{1})f(x) for x ∈ V^{+}.

Therefore

⟨df, df⟩_{1} = ⟨d^{∗}df, f⟩_{0}
= ⟨Δf, f⟩_{0}
= ∑_{x∈V} Δff
= ∑_{x∈V^{+}} Δff
≤ ∑_{x∈V^{+}}(k − μ_{1})f(x)f(x)
= (k − μ_{1})⟨f, f⟩_{0}.

Hence

2\sqrt{k}⟨f, f⟩_{0}^{1/2}\sqrt{k − μ_{1}}⟨f, f⟩_{0}^{1/2} ≥ h(X)⟨f, f⟩_{0}.  (3.16)

Finally

\sqrt{2k(k − μ_{1})} ≥ h(X).  (3.17)

Since we wanted our graphs to have large h(X) we can rephrase the main problem.

3.1. Rephrasing the main problem using eigenvalues

Give explicit constructions of families (X_{m})_{m≥1} of finite connected k-regular graphs with the following properties.

1. |V_{m}| → ∞ as m → ∞

2. ∃c > 0 such that k − μ_{1} ≥ c for every m ≥ 1.

A family of k-regular graphs is a family of expanders if and only if the spectral gap is bounded away from zero. However it turns out that the spectral gap cannot be too large since we have a lower bound for μ_{1} according to the next theorem proved below.

Theorem 2. Let (X_{m})_{m≥1} be a family of connected k-regular finite graphs with |V_{m}| → ∞ as m → ∞ then

lim inf_{m→∞} μ_{1}(X_{m}) ≥ 2\sqrt{k − 1}.  (3.18)

This means that for a large connected k-regular graph, its μ_{1} is either ≥ 2\sqrt{k − 1} or not much smaller than 2\sqrt{k − 1}. Actually an improved version of this theorem can be found in [6]; theorem 1.4.9. It shows that not only the first nontrivial eigenvalue becomes asymptotically larger than 2\sqrt{k − 1}, but actually there is a positive proportion of eigenvalues in any interval [(2 − ϵ)\sqrt{k − 1}, k]. We will prove Theorem 2 below.

Definition. The diameter of a graph X is the distance, i.e. shortest path length, between two furthest vertices in X.

Theorem 3. Let X be a k-regular graph with n vertices and diameter d. If X is not bipartite, then

d ≤ \frac{log(n − 1)}{log(k/λ(X))} + 1

where λ(X) is the maximum of the absolute values of all the nontrivial eigenvalues.

□

This theorem due to Chung [5] shows that one can minimize the diameter by minimizing λ(X). Hence for our purposes in optimal communication networks we prefer graphs with small diameters.

The diameter of a graph plays an important role.

Proposition 4. If X is a connected, k-regular graph with diameter d, then X contains at most

1 + k + k(k − 1) + k(k − 1)^{2} + … + k(k − 1)^{d−1}

vertices which is known as the Moore bound.

□

Theorem 4. [15] Let X be a finite, connected and k-regular graph with diameter ≥ 2l + 2 ≥ 4. Then

μ_{1}(X) ≥ 2\sqrt{k − 1} − \frac{2\sqrt{k − 1} − 1}{l}  (3.19)

Proof. We will use the fact that

⟨df, df⟩_{1} ≥ (k − μ_{1})⟨f, f⟩_{0}  (3.20)

for any nonzero function f on V perpendicular to the constant function. By the assumption there are two vertices u and w in V such that dist(u, w) ≥ 2l + 2 ≥ 4. Let us define for 0 ≤ i ≤ l:

U_{i} = {x ∈ V : dist(u, x) = i}
W_{i} = {x ∈ V : dist(w, x) = i}

Note that U_{0}, U_{1}, …, U_{l} and W_{0}, W_{1}, …, W_{l} are mutually disjoint. Further no vertices in ⋃_{i=0}^{l} U_{i} are adjacent to ⋃_{i=0}^{l} W_{i}.

Let us consider

f(x) = \{ \begin{matrix}a & for x ∈ U_{0} ⋃ U_{1}; \\ a(k − 1)^{−(i−1)/2} & for x ∈ U_{i}, i = 1, …, l ; \\ −b & for x ∈ W_{0} ⋃ W_{1}; \\ −b(k − 1)^{−(i−1)/2} & for x ∈ W_{i}, i = 1, …, l ; \\ 0 & otherwise. \end{matrix} \}

where a, b are any positive constants such that ∑_{x∈V} f(x) = 0.

Now let us start with the right hand side of 3.20.

⟨f, f⟩_{0} = ∑_{x∈V} f(x)^{2} = ∑_{x∈U} f(x)^{2} + ∑_{x∈W} f(x)^{2} = A_{1} + B_{1}.  (3.21)

At first we estimate a lower bound for A_{1}.

A_{1} = ∑_{x∈U} f(x)^{2}
= a^{2} + a^{2}|U_{1}| + ∑_{i=2}^{l} a^{2}(k − 1)^{−(i−1)}|U_{i}|
= a^{2}(1 + ∑_{i=1}^{l}(k − 1)^{−(i−1)}|U_{i}|.

Since each vertex in U_{i−1} has at least one neighbor in U_{i−1} and at most k−1 neighbors in U_{i} it follows that:

|U_{i}| ≤ (k − 1)|U_{i−1}|.

Hence

|U_{i}| ≥ \frac{|U_{i+1}|}{k − 1} ≥ \frac{|U_{i+2}|}{(k − 1)^{2}} ≥ … ≥ \frac{|U_{l}|}{(k − 1)^{l−i}} .  (3.22)

Therefore by the above

|A_{1}| ≥ a^{2}(1 + ∑_{i=1}^{l}(k − 1)^{−(i−1)} \frac{|U_{l}|}{(k − 1)^{l−i}})
≥ a^{2}(1 + l\frac{|U_{l}|}{(k − 1)^{l−1}} ).

Similarly we get

|B_{1}| ≥ b^{2}(1 + l\frac{|W_{l}|}{(k − 1)^{l−1}} ).

Now we will concentrate on the left hand side of 3.20.

⟨df, df⟩_{1} = ∑_{e∈E} df(e)^{2}
= ∑_{e∈E}(f(e^{+}) − f(e^{−}))^{2}
= ∑_{e∈E,e^{+} or e^{−}∈U}(f(e^{+}) − f(e^{−}))^{2} + ∑_{e∈E,e^{+} or e^{−}∈W}(f(e^{+}) − f(e^{−}))^{2}
= A_{2} + B_{2}.

Now we will estimate an upper bound on A_{2} and B_{2}.

A_{2} = ∑_{i=1}^{l−1}(k − 1)|U_{i}|(a(k − 1)^{−(i−1)/2} − a(k − 1)^{−i/2})^{2} + (k − 1)|U_{l}|(a(k − 1)^{−(l−1)/2} − 0)^{2}

= a^{2} ∑_{i=1}^{l−1} |U_{i}|(k − 1)(k − i)^{−i}(\sqrt{k − 1} − 1)^{2} + a^{2}|U_{l}|(k − 1)(k − 1)^{−(l−1)}

= (\sqrt{k − 1} − 1)^{2}a^{2}(∑_{i=1}^{l} \frac{|U_{i}|}{(k − 1)^{i−1}} ) + a^{2}(2\sqrt{k − 1} − 1)\frac{|U_{l}|}{(k − 1)^{l−1}}

≤ (\sqrt{k − 1} − 1)^{2}a^{2}(∑_{i=1}^{l} \frac{|U_{i}|}{(k − 1)^{i−1}} ) + a^{2}(2\sqrt{k − 1} − 1)\frac{|U_{l}|}{(k − 1)^{l−1}}

≤ (\sqrt{k − 1} − 1)^{2}(A_{1} − a^{2}) + (2\sqrt{k − 1} − 1)\frac{(A_{1} − a^{2})}{l}

< (\sqrt{k − 1} − 1)^{2}A_{1} + (2\sqrt{k − 1} − 1)\frac{A_{1}}{l}

= (k − 2\sqrt{k − 1} + \frac{2\sqrt{k − 1} − 1}{l})A_{1}.

And similarly

B_{2} = k − 2\sqrt{k − 1} + (\frac{2\sqrt{k − 1} − 1}{l})B_{1}.

If we plug A_{1}, A_{2}, B_{1}, B_{2} into 3.20, we get

k − μ_{1}(X) < \frac{A_{2} + B_{2}}{A_{1} + B_{1}} .

Hence

k − μ_{1}(X) < \frac{(k − 2\sqrt{k − 1} + \frac{2\sqrt{k−1}−1}{l})(A_{1} + B_{1})}{(A_{1} + B_{1})}

therefore

2\sqrt{k − 1} − \frac{2\sqrt{k − 1} − 1}{l} < μ_{1}(X).  (3.23)

Note that if |V_{m}| → ∞ then the diameter goes infinity, hence l → ∞. Then theorem 2 follows.

Definition. The girth of a connected graph X, denoted by g(X), is the length of the shortest circuit in X. We will say that g(X) = ∞ if X has no circuit, that is, if X is a tree.

Theorem 5. Let (X_{m})_{m≥1} be a family of connected, k-regular, finite graphs, with g(X_{m}) → ∞ as m → ∞ if μ denotes smallest eigenvalue ≠ −k then

lim sup_{m→∞} μ(X_{m}) ≤ −2\sqrt{k − 1}.  (3.24)
□

The proof of this theorem is analogous to the proof of Theorem 4. Theorem 2 and theorem 5 single out an extremal condition on finite k-regular graphs which leads to the idea of Ramanujan graphs.

Definition. A finite connected k-regular graph X is a Ramanujan graph if for every nontrivial eigenvalue μ ≠ −k of X one has |μ| ≤ 2\sqrt{k − 1}.

The condition that X is Ramanujan is equivalent to the Riemann hypothesis for Ihara Zeta function, see [14] of X which is also discrete analog of Selberg Zeta functions.

Example. A complete graph is Ramanujan since it has only one nontrivial eigenvalue -1 and it lie the Ramanujan interval. However these are not good enough for our purposes since k = n − 1 tends to infinity as n tends to infinity. Families of kregular Ramanujan graphs with number of vertices tending to infinity form a family of expanders for k ≥ 3 since k − 2\sqrt{k − 1} > 0. From the spectral point of view Ramanujan graphs are the preferable.

However we just know explicit constructions of infinite families of k-regular Ramanujan graphs for k = p^{n} + 1, where p is a prime number. The smallest unknown case is when k = 7. In this paper we try to give a known construction of a family of (p + 1)-regular Ramanujan graphs where p is an odd prime. While constructing an infinite family of k-regular Ramanujan graphs is a challenging research area for mathematicians there is another interesting open problem. Is it true that almost every k-regular graph is Ramanujan? More formally, is it true that any family random k-regular graph of size n, G_{n}, satisfies

lim_{n→∞} P r(μ_{1}(G_{n}) ≤ 2\sqrt{k − 1}) = 1.  (3.25)

In [7] Friedman proves,

Theorem 6. For every ε > 0,

lim_{n→∞} P r(μ_{1}(G_{n}) ≤ 2\sqrt{k − 1} + ε) = 1  (3.26)

where G_{n} is a random k-regular graph of size n.

□

The proof of this theorem is quite involved and is based on analysis of expected value of the modified trace of high powers of adjacency matrices. Friedman uses that argument in his paper for various models of randomness.

4. Construction of X^{p,q}

In this section we will give an explicit construction for families of expanders which we will denote by X^{p,q} by using Cayley graphs and we will also describe when these constructions result in Ramanujan graphs. These Cayley graphs are a special class of k-regular graphs constructed using group theory and the integral quaternions H(Z). Since these graphs are built from a particular group G, we can use this underlying group to analyze the properties of the graph. In chapter two we showed that a random graph is an expander with a probability greater than zero and we also mentioned that choosing a few graphs with that property will give expanders with probability close to 1, however it is a challenging problem to give the explicit construction of a family of graphs which are also expanders.

Let G be a group and let S be a nonempty finite subset of G. We assume that S is symmetric that is S^{−1} = S.

Definition. The Cayley graph X(G, S) is the graph with the vertex set V = G and the edge set

E = {{x, y} : x, y ∈ G : ∃s ∈ S : y = xs}

Example. : Let us take G = Z/6Z and S = {−1, 1}. Then the Cayley graph X(G, S) is the cycle graph on 6 vertices.

Example. Li constructed in her paper [12] Cayley graphs which are also Ramanujan in the following way: Let G = F_{q} and S = {x ∈ G : norm(x) = 1}. S is a symmetric subset of G and the Cayley graph X(G, S) is Ramanujan which can be shown by using the Weil estimates on Kloosterman sums. In this family k is not fixed.

Proposition 5. Let X(G, S) be a Cayley graph; set k = |S|.

a) X(G, S) is a simple, k-regular graph. b) X(G, S) has no loops if and only if 1 is not in S.

c) X(G, S) is connected if and only if S generates G.

Proof. a) Let us look at the adjacency matrix of X(G, S)

A_{xy} = \{ \begin{matrix}1 & if there exists s ∈ S such that y = xs; \\ 0 & otherwise. \end{matrix} \}

It is clear that X(G, S) is simple and k-regular. b) (x, x) is an edge if and only if x = x1 if and only if 1 ∈ S. Obviously X(G, S) does not have a loop if and only if 1 is not in S.

c) X(G, S) is connected if and only if every x ∈ G is connected to 1 ∈ G by a path. But this holds if and only if every x ∈ G can be expressed as a word on the alphabet S(a finite string on elements of S) , that is if and only if S generates G.

Before starting with the construction of our Cayley graphs we would like to emphasize the importance of the Cayley graphs in solving the problem of constructing families of expander graphs.

Theorem 7. For every 0 < ρ < 1 there exists c = c(ρ) > 0 such that for every group G of order n, and for a set S of c(ρ) log n random elements in the group, the expected value of the second largest value of the normalized adjacency matrix Â = \frac{1}{|S|}A of the Cayley graph X(G, S) is at most (1 − ρ).

□

Corollary 1. For every 0 < ε < 1 there exists a c(ε) > 0 such that the following holds. Let G be a group of order n, and let S be a random set of c(ε) log_{2} n elements of G, then the Cayley graph X(G, S) is an (n, k, ε(ρ))-expander almost surely. (i.e. the probability it is such an expander tends to 1 as n tends to infinity.)

□

The proof of the corollary 1 and the theorem 7 can be found in [3].

4.1. Background on integral quaternions: H(Z)

Definition. The integral quaternion algebra, denoted by H(Z), is the algebra given by the following:

1. H(Z) = {a_{0} + a_{1}i + a_{2}j + a_{3}k : a_{0}, a_{1}, a_{2}, a_{3} ∈ Z};

2. 1 is the multiplicative unit;

3. i^{2} = j^{2} = k^{2} = −1;

4. ij = −ji = k; jk = −kj = i; ki = −ik = j.

Remark: These are naive integral quaternions of Lipschitz and not Hurwitz integral quaternions which make a maximal order.

If q = a_{0}+a_{1}i+a_{2}j+a_{3}k is a quaternion then its conjugate is \overline{q} = a_{0}−a_{1}i−a_{2}j−a_{3}k and the norm of q is N(q) = q\overline{q} = \overline{q}q = a_{0}^{2} + a_{1}^{2} + a_{2}^{2} + a_{3}^{2}. Note that the quaternion norm is multiplicative, that is N(q_{1}q_{2}) = N(q_{1})N(q_{2}). Hence we get the ‘if part’ of the following theorem.

Theorem 8. δ ∈ H(Z) is prime in H(Z) if and only if N(δ) is prime in Z.

The proof can be found in [6]. □ We will restrict our attention to the set of integral quaternions δ, where N(δ) = p^{k},

where p is an odd rational prime. So let p be an odd prime by Jacobi’s theorem the equation a_{0}^{2} +a_{1}^{2} +a_{2}^{2} +a_{3}^{2} = p has 8(p+1) solutions, each corresponding to an integral quaternion δ = a_{0} + a_{1}i + a_{2}j + a_{3}k of norm p. The units in H(Z) are ±1, ±i, ±j, ±k which implies that there are (p + 1) non associated primes in H(Z) with norm p i.e. up to associates there are (p + 1) solutions to the equation a_{0}^{2} + a_{1}^{2} + a_{2}^{2} + a_{3}^{2} = p. If p ≡ 1 (mod 4), one a_{i} is odd while the others are even; if p ≡ 3 (mod 4), one a_{i} is even while the rest are odd.

Case 1: If p ≡ 1 (mod 4) assume that a_{0} is odd. a_{0} > 0 then if δ is a prime then \overline{δ} is also a prime and δ ≡ 1 (mod 2). We have representatives for the primes δ_{1}, \overline{δ_{1}}, …, δ_{\frac{p+1}{2}} , \overline{δ_{\frac{p+1}{2}}} .

Case 2: If p ≡ 3 (mod 4) among a_{0}, a_{1}, a_{2}, a_{3} one is even, other are odd. Assume a_{0} is even and a_{0} > 0 then again if δ is a prime then so is \overline{δ}. Assume a_{0} = 0 then \overline{δ} = −δ. Choose one among two and call it β. For this case δ ≡ i + j + k (mod 2).

Hence there are p + 1 solutions of the equation

a_{0}^{2} + a_{1}^{2} + a_{2}^{2} + a_{3}^{2} = p  (4.1)

such that the corresponding quaternion δ satisfies either δ ≡ 1 (mod 2) or δ ≡ i+j+k (mod 2). In this list of solutions, both δ_{t} and \overline{δ_{t}} appear whenever a_{0} > 0, while only one of the pair is included when a_{0} = 0. We thus form the set

S_{p} = \{α_{1}, \overline{α_{1}}, …, α_{s}, \overline{α_{s}}, β_{1}, …, β_{t}\}  (4.2)

where 2s + t = p + 1 and S_{p} is the set of primes in H(Z) of norm p.

Definition. A reduced word over S_{p} is a word over the alphabet S_{p}, which can’t be reduced of the form α_{i}\overline{α_{i}}, β_{j}^{2}(i = 1, 2, …, s, j = 1, 2, …, t).

Let p, q be distinct odd primes. Fix an odd prime p. We are going to construct an infinite family of (p + 1)-regular Ramanujan graph X^{p,q} by varying the odd primes q.

We now consider the reduction modulo q:

τ_{q}: H(Z) → H(F_{q})

Let us define ψ_{q}: H(F_{q}) → M_{2}(F_{q}) by

ψ_{q}(a_{0} + a_{1}i + a_{2}j + a_{3}k) = [\begin{matrix}a_{0} + a_{1}x + a_{3}y & −a_{1}y + a_{2} + a_{3}x \\ −a_{1}y − a_{2} + a_{3}x & a_{0} − a_{1}x − a_{3}y \end{matrix}]  (4.3)

where x, y ∈ F_{q} such that x^{2} + y^{2} + 1 ≡ 0 (mod q).

This isomorphism has two important properties: a) N(α) = det(ψ_{q}(α)) for α ∈ H(F_{q});

b) If α = \overline{α} for α ∈ H(F_{q}) then ψ_{q}(α) is a scalar matrix.

For α ∈ S_{p} ⊂ H(Z), N(α) = p ≠ q. So ψ(τ(α)) ∈ GL_{2}(F_{q}) as det(ψ(τ(α))) ≠ 0. We have the canonical map

φ: GL_{2}(F_{q}) → PGL_{2}(F_{q})

whose kernel is exactly the subgroup of scalar matrices.

We then set

S_{p,q} = (φoψ_{q}oτ_{q})(S_{p})

Let us summarize everything with the following diagram.

[figure: H(Z); τ_{q}; H(F_{q}); ψ_{q}; M_{2}(F_{q}); S_{p}; H(F_{q})^{×}; ∼; GL_{2}(F_{q}); φ; PGL_{2}(F_{q})]  (4.4)

Lemma 1. If q is large enough with respect to p (for example,if q > 2\sqrt{p}), then |S_{p,q}| = p + 1.

Proof. Let us take two distinct elements α and β of S_{p}, where α = a_{0}+a_{1}i+a_{2}j+a_{3}k and β = b_{0} + b_{1}i + b_{2}j + b_{3}k. Then there is an r ∈ {0, 1, 2, 3} such that a_{r} ≠ b_{r}. Since N(α) = N(β) = p we have a_{r}, b_{r} ∈ (−\sqrt{p}, \sqrt{p}) for every r ∈ \{0, 1, 2, 3\}, so if q > 2\sqrt{p} we have a_{r} not congruent b_{r} (mod q), and τ_{q}(α) ≠ τ_{q}(β). Now set A = (ψoτ_{q})(α) and B = (ψoτ_{q})(β) so that A ≠ B in GL_{2}(F_{q}). Assume by contradiction that φ(A) = φ(B). Then there exists λ ∈ F_{q}^{×} such that λ ≠ 1 and A = λB. If we take the determinants of both sides then we get p = detA = λ^{2}detB = λ^{2}p; hence λ^{2} = 1, or λ = −1 since A ≠ B. Hence A = −B and we get α ≡ −β (mod q). Since q > 2\sqrt{p} we deduce a_{i} = −b_{i}, showing that α = −β. By assumption a_{0}, b_{0} ≥ 0, so a_{0}, b_{0} = 0 and hence β = −\overline{α}. But this contradicts the definition of S_{p} since if α ∈ S_{p} has a_{0} = 0 then \overline{α} is not in S_{p}. Therefore |S_{p,q}| = |S_{p}| = p + 1 Proposition 6. If (\frac{p}{q}) = 1 then S_{p,q} is a symmetric subset of PSL_{2}(F_{q}) and if (\frac{p}{q}) = −1 of PGL_{2}(F_{q}) .

Proof. We have shown that S_{p} has the form

S_{p} = \{α_{1}, \overline{α_{1}}, …, α_{s}, \overline{α_{s}}, β_{1}, …, β_{t}\}

where 2s + t = p + 1.

Case 1: For all α = a_{0} + a_{1}i + a_{2}j + a_{3}k ∈ S_{p} such that a_{0} > 0 we have shown that \overline{α} is also an element of S_{p}. Therefore for all α ∈ S_{p} such that a_{0} > 0, φoψ_{q}oτ_{q}(α) and φoψ_{q}oτ_{q}(\overline{α}) are elements of S_{p,q}. Furthermore

[φoψ_{q}oτ_{q}(α)][φoψ_{q}oτ_{q}(\overline{α})] = φoψ_{q}oτ_{q}(α\overline{α})

Since ψ_{q}oτ_{q}(α\overline{α}) is a scalar matrix ψ_{q}oτ_{q}(α\overline{α}) ∈ ker(φ). Since φ is an isomorphism the kernel is the trivial one, hence by the above equation

[φoψ_{q}oτ_{q}(α)]^{−1} = [φoψ_{q}oτ_{q}(\overline{α})]

Case 2: Let us take β = b_{0} + b_{1}i + b_{2}j + b_{3}k ∈ S_{p} such that b_{0} = 0 then we have shown that \overline{β} = −β is not an element of S_{p}.

[φ ∘ ψ_{q} ∘ τ_{q}(β)] · [φ ∘ ψ_{q} ∘ τ_{q}(β)] = φ ∘ ψ_{q} ∘ τ_{q}(β · β)
= φ ∘ ψ_{q} ∘ τ_{q}(−β\overline{β})
= φ(−ψ_{q}(τ_{q}(β\overline{β})))
= φ (− (\begin{matrix}λ & 0 \\ 0 & λ \end{matrix})) = 1

Thus, [φ ∘ ψ_{q} ∘ τ_{q}(β)]^{−1} = [φ ∘ ψ_{q} ∘ τ_{q}(β)].

Therefore for all [φoψ_{q}oτ_{q}(s)] in S_{p,q}, [φoψ_{q}oτ_{q}(s)]^{−1} is also in S_{p,q}. S_{p,q} is a symmetric subset of PGL_{2}(F_{q}).

Now let us show that S_{p,q} is contained in PSL_{2}(F_{q}) if (\frac{p}{q}) = 1. For any α ∈ S_{p} ψ_{q}(τ_{q}(α)) ∈ GL_{2}(F_{q}) where the determinant is p = b^{2}( mod q) for some b ∈ Z_{q}. Then

φ(ψ_{q}(τ_{q}(α))) = φ(( \begin{matrix}b^{−1} & 0 \\ 0 & b^{−1} \end{matrix} ) (ψ_{q}(τ_{q}(α)))

Since

( \begin{matrix}b^{−1} & 0 \\ 0 & b^{−1} \end{matrix} ) (ψ_{q}(τ_{q}(α)) ∈ SL_{2}(F_{q}), φ(( \begin{matrix}b^{−1} & 0 \\ 0 & b^{−1} \end{matrix} ) (ψ_{q}(τ_{q}(α)))) ∈ PSL_{2}(F_{q})

Thus for every α ∈ S_{p} if (\frac{p}{q}) = 1 then φ(ψ_{q}(τ_{q}(α))) is an element of PSL_{2}(F_{q}) hence S_{p,q} = φ(ψ_{q}(τ_{q}(S_{p}))) ⊂ PSL_{2}(F_{q}). Furthermore, if (\frac{p}{q}) = −1 then there is no b such that p ≡ b^{2} (mod q), hence there is no element A ∈ GL_{2}(F_{q}) such that det[A(ψ_{q}(τ_{q}(α)))] = 1. Thus if (\frac{p}{q}) = −1 then for all α ∈ S_{p} ψ_{q}(τ_{q}(α)) can not be congruent to any matrix with determinant 1 in PGL_{2}(F_{q}), hence φ(ψ_{q}(τ_{q}(α))) ∈ PGL_{2}(F_{q}) − PSL_{2}(F_{q}). Thus if p is not a square modulo q then S_{p,q} ⊂ PGL_{2}(F_{q}) − PSL_{2}(F_{q}).

Now we can define the graph X^{p,q}

Definition. Given odd primes p and q, we define X^{p,q} as the Cayley graph of PSL_{2}(F_{q}) with respect to S_{p,q} if (\frac{p}{q}) = 1 and as the Cayley graph of PGL_{2}(F_{q}) with respect to S_{p,q} if (\frac{p}{q}) = −1.

4.2. Properties of X^{p,q}

We have shown that |S_{p}| = |S_{p,q}| = p + 1. We will see by the following important theorem that the regularity of the graphs X^{p,q} remains equal to p + 1 as q varies and this graph can be used to generate infinitely many (p + 1)-regular graphs.

Theorem 9. Let p, q be distinct, odd primes with p ≥ 5, q ≥ p^{8}. The graphs X^{p,q} are (p + 1)-regular graphs which are connected, (n, p + 1, c)-expanders( See Corollary 4 for bound for the constant c) and, are Ramanujan graphs.

Moreover

a)if (\frac{p}{q}) = 1, then X^{p,q} has \frac{q(q^{2}−1)}{2} vertices and it satisfies the girth estimate g(X^{p,q}) ≥ 2 log_{p} q.

b)if (\frac{p}{q}) = −1 then X^{p,q} is a graph with n = q(q^{2} − 1) vertices and it satisfies the girth estimate g(X^{p,q}) ≥ 4 log_{p} q − log_{p} 4.

Proof. Some parts of this theorem are easy to prove. Since X^{p,q} is the Cayley graph with respect to S_{p,q} by the definition of the Cayley graphs we know that the cardinality of |S_{p,q}| is equal to the regularity of the graph. Hence X^{p,q} is (p + 1)-regular. The proof of |V (X^{p,q})| = q(q^{2} − 1)/2 or q(q^{2} − 1) follows directly from the cardinality of PSL_{2}(F_{q}) and PGL_{2}(F_{q}) respectively. The proof of the girth estimates is not hard and can be found in [6]. However the proof of being Ramanujan relies on deep number theoretic results and is beyond the scope of this paper. So it remains to prove:

1. X^{p,q} is connected, or equivalently that S_{p,q} generates PSL_{2}(F_{q}) when p is a square modulo q, and PGL_{2}(F_{q}) when p is not a square modulo q.

2. X^{p,q} is an expander.

We proceed to prove the main theorem above in the rest of this chapter.

4.3. The graph Y^{p,q} and its connection with X^{p,q}

Definition. For an odd prime p, let Λ′ be the subset of the integral quaternions.

Λ′ = \{α ϵ H(Z) \begin{matrix}| & α ≡ 1 mod 2 or α ≡ i + j + k mod 2, \\ | & and N(α) = p^{m} for some value m \end{matrix} \}  (4.5)

Definition. For all α, β ϵ Λ′, define the equivalence relation ∼ as follows:

α ∼ β ⇔ p^{m}α = ±p^{n}β  (4.6)

where m, n are integers.

Let [α] denote the equivalence class of α and let Λ = Λ′/ ∼ be the set of equivalence classes. Let Q be the quotient map from Λ′ → Λ such that Q(α) = [α]. By definition of the set S_{p} it is obvious that S_{p} ⊂ Λ′. Also note that ∼ is compatible with multiplication, that is if α_{1} ∼ β_{1}, α_{2} ∼ β_{2}, then α_{1}α_{2} ∼ β_{1}β_{2}.

Proposition 7. a) Λ is a group.

b) The Cayley graph X(Λ, Q(S_{p})) is the p + 1-regular tree.

Proof. a)For α ∈ Λ′ : α\overline{α} = \overline{α}α ∼ 1, hence, [α]^{−1} = [α], so Λ is a group. For the proof of b we will need the following theorem, see [6].

Theorem 10. For all α ϵ Λ′ with N(α) = p^{k}, α has a unique factorization, α = ±p^{r}w_{m}, where r is a natural number, w_{m} is a reduced word of length m over S_{p}, and 2r + m = k.

□

b) For α, β ∈ Λ′, it is easy to show that α ∼ β implies that α = β. So |Q(S_{p})| = p + 1. By the existence part of the above theorem and the definition of ∼ any α ∈ Λ′ is equivalent to a reduced word over S_{p}. Thus, Q(S_{p}) generates Λ, which implies X(Λ, Q(S_{p})) is connected and p + 1-regular. To prove that it is a tree, we have to show that it does not contain any circuit. So suppose by contradiction that it does contain a circuit x_{0}, x_{1}, …, x_{g} = x_{0} of length g ≥ 3. Assume x_{0} = [1]. Thus, x_{1} = x_{0}[s_{1}] = [s_{1}], x_{2} = x_{1}[s_{2}] = [s_{1}s_{2}], …, and x_{g} = [s_{1}s_{2} … s_{g}] = [1] for some word s_{1}s_{2} … s_{g}, of length g in S_{p}. Thus, 1p^{m} = ±p^{n}s_{1}s_{2} … s_{g}. This contradicts the uniqueness of the factorization of α for every α in Λ′. Thus, X(Λ, Q(S_{p})) contains no cycles of length greater or equal to 3. X(Λ, Q(S_{p})) is a tree.

As in section 4.1 we consider reduction modulo q:

τ_{q}: H(Z) → H(F_{q})

which sends Λ′ to the group H(F_{q})^{×} of invertible elements in H(F_{q}). If α, β ∈ Λ′ and α ∼ β which implies that αp^{m} = ±βp^{n}. Let us assume without loss of generality that n > m then τ_{q}(α) = τ_{q}(±p^{n−m})τ_{q}(β), and hence taking modulo F_{q}^{×}, τ_{q}(α) = τ_{q}(β). In other words equivalent elements in Λ′ have the same image in H(F_{q})^{×}/F_{q}^{×}. Hence we obtain a well defined map

π_{q}: Λ → H(F_{q})^{×}/F_{q}^{×}  (4.7)

given by π_{q}([α]) = τ_{q}(α)( mod F_{q}^{×}). Note that π_{q} is a group homomorphism. We will denote the image of [S_{p}] in H(F_{q})^{×}/F_{q}^{×} by T_{p,q}. Furthermore, since Q(S_{p}) generates Λ′, T_{p,q} = π_{q}(Q(S_{p})) generates π_{q}(Λ). Let us denote by Λ(q) the kernel of π_{q}, which is a normal subgroup of Λ. So by the Fundamental Group Homomorphism Theorem, Λ/Λ(q) ≅ π_{q}(Λ). Let us denote by β the isomorphism from H(F_{q})^{×}/F_{q}^{×} to GL_{2}(F_{q})/F_{q}^{×} = PGL_{2}(F_{q}) induced from the isomorphism ψ_{q} : H(F_{q})^{×} to GL_{2}(F_{q}). Then β(T_{p,q}) = S_{p,q}. In particular |T_{p,q}| = |S_{p,q}|, which is p + 1 if q > 2\sqrt{p}. Thus for q > 2\sqrt{p} the Cayley Graph Y^{p,q} = X(π_{q}(Λ), T_{p,q}) is a connected, p + 1-regular graph. As we can see from the diagram below S_{p,q} = β(T_{p,q}). Thus, S_{p,q} generates the subgroup β(Λ/Λ(q)) of PGL_{2}(F_{q}) and the Cayley graph X(β(Λ/Λ(q), S_{p,q})) ≅ Y^{p,q} is a connected component of X^{p,q}. To prove that X^{p,q} is connected we will show that Y^{p,q} is connected and then use the fact to prove X^{p,q} is also connected. Before starting with the proof let us look at the following commutative diagram which summarizes all the previous definitions.

[figure: H(Z); τ_{q}; H(F_{q}); ψ_{q}; M_{2}(F_{q}); S_{p}; Q; Λ′; τ_{q}; H(F_{q})^{×}; ψ_{q}; GL_{2}(F_{q}); ρ; \frac{S_{p}}{∼}; Λ; π_{q}; T_{p,q}; \frac{H(F_{q})^{×}}{F_{q}^{×}}; β; S_{p,q}; \frac{GL_{2}(F_{q})}{F_{q}^{×}}; G(Λ, Q(S_{p})); Y^{p,q} = G(π_{q}(Λ), T_{p,q}); X^{p,q}]

(4.8)

Note that GL_{2}(F_{q})/F_{q}^{×} = PGL_{2}(F_{q}).

We mentioned that proving that X^{p,q} is connected is the same as proving that S_{p,q} generates PSL_{2}(F_{q}) when (\frac{p}{q}) = 1, and PGL_{2}(F_{q}) when (\frac{p}{q}) = −1, it suffices to show

β(Λ/Λ(q)) = \{ \begin{matrix}PSL_{2}(F_{q}) if (\frac{p}{q}) & = 1 \\ PGL_{2}(F_{q}) if (\frac{p}{q}) & = −1 \end{matrix}  (4.9)

Let H = β(Λ/Λ(q)) ∩ PSL_{2}(F_{q}). To prove the above equation when (\frac{p}{q}) = 1, it suffices to show H = PSL_{2}(F_{q}).

When (\frac{p}{q}) = −1, S_{p,q} ⊂ PGL_{2}(F_{q}) − PSL_{2}(F_{q}) (see the proof of prop 4). From the cardinality of PGL_{2}(F_{q}) and PSL_{2}(F_{q}), it follows that PSL_{2}(F_{q}) is a subgroup of PGL_{2}(F_{q}) of index 2. The two cosets of PSL_{2}(F_{q}) partition PGL_{2}(F_{q}). Suppose S_{p,q} generates PSL_{2}(F_{q}). If there exists an element α ϵ S_{p,q} such that α ∉ PSL_{2}(F_{q}), then αPSL_{2}(F_{q}) = PGL_{2}−PSL_{2}(F_{q}). This would imply that S_{p,q} generates all of PGL_{2}(F_{q}). If (\frac{p}{q}) = −1, such an α exists. Thus, in the (\frac{p}{q}) = −1 case, it also suffices to show H = β(Λ/Λ(q)) ∩ PSL_{2}(F_{q}) = PSL_{2}(F_{q}). The proof that H = PSL_{2}(F_{q}) follows from theorem 11, see [6].

Definition. A group is metabelian if it admits a normal subgroup N such thaht both N and G/N are abelian. Theorem 11. If p is prime and H is a proper subgroup of PSL_{2}(F_{q}) with |H| > 60, then H is metabelian.

□

Thus, if |H| > 60 and H is not metabelian, then H is not proper, i.e. H = PSL_{2}(F_{q}). We can prove |H| greater than 60 using the assumption p ≥ 5, q > p^{8}, and the following two observations:

1. |PGL_{2}(F_{q})| ≥ |β(Λ/Λ(q)) · PSL_{2}(F_{q})| = \frac{|β(Λ/Λ(q))|·|PSL_{2}(F_{q})|}{|H|} where β(Λ/Λ(q)) · PSL_{2}(F_{q}) = {ab : a ϵ β(Λ/Λ(q)) and b ϵ PSL_{2}(F_{q})}

2. |β(Λ/Λ(q))| = |Y^{p,q}| ≥ \frac{p}{q} We use the following result to prove H is not metabelian. Lemma 2. If G is metabelian, then [[g_{1}, g_{2}], [g_{3}, g_{4}]] = 1, ∀ g_{1}, g_{2}, g_{3}, g_{4} ϵ G.

□

If (\frac{p}{q}) = 1 choose h_{1}, h_{2}, h_{3}, and h_{4} ϵ H as follows:

1. let h_{1} be any element of S_{p,q}

2. h_{2} ≠ h_{1}^{±1}, h_{2} ϵ S_{p,q}

3. h_{3} = h_{1}

4. h_{4} ∉ {h_{1}^{±1}, h_{2}^{±1}}, h_{4} ϵ S_{p,q} Thus [[h_{1}, h_{2}], [h_{3}, h_{4}]] is a reduced word of length 16 in S_{p,q}. The preimage of this word is a reduced word of length 16 in T_{p,q}. If [[h_{1}, h_{2}], [h_{3}, h_{4}]] = [1], then the preimage = [1] in T_{p,q}. Using a similar argument we used in the proof of the second part of Proposition 5, we can show this word of length 16 in T_{p,q} corresponds to a cycle of length ≤ 16 in Y^{p,q}. Similarly, if (\frac{p}{q}) = −1, we can chose h_{1}, h_{2}, h_{3}, h_{4} ϵ H such that if [[h_{1}, h_{2}], [h_{3}, h_{4}]] = [1], then there exists a cycle of length ≤ 24 in Y^{p,q}. We can prove, see [6], the following lower bounds on the girth of Y^{p,q}.

g(Y^{p,q}) ≥ \{ \begin{matrix}2 log_{p} q  if (\frac{p}{q}) = & 1 \\ 4 log_{p} q − log_{p} 4 if (\frac{p}{q}) = & −1 \end{matrix}  (4.10)

Thus, for p ≥ 5, q > p^{8}

g(Y^{p,q}) ≥ \{ \begin{matrix}2 log_{p} q > 16 if (\frac{p}{q}) = & 1 \\ 4 log_{p} q − log_{p} 4 > 24 if (\frac{p}{q}) = & −1 \end{matrix}

Therefore, [[h_{1}, h_{2}], [h_{3}, h_{4}]] can not equal [1], which implies H is not metabelian. Thus, H = PSL_{2}(F_{q}) and S_{p,q} generates PSL_{2}(F_{q}) when (\frac{p}{q}) = 1, and PGL_{2}(F_{q}) when (\frac{p}{q}) = −1, which implies X^{p,q} is connected.

We still have to prove that the X^{p,q}’s are a family of expanders. In order to prove this we need some basic background which will lead to the trace formula for X^{p,q}. This formula will play an important role in the proof. On our way to the definition of the trace for X^{p,q} we will only state the theorems and propositions since the proofs of these theorems are not in the scope of this paper and can be found in [6].

Definition. Let X(V, E) be a k-regular, simple graph with |V | possibly infinite. A path of length r without backtracking in X is a sequence \underline{e} = (x_{0}, x_{1}, …, x_{r}) of vertices in V s.t. x_{i} is adjacent to x_{i+1} (i = 0, 1, …, r) and x_{i+1} ≠ x_{i−1}. The origin of \underline{e} is x_{0} and the extremity of \underline{e} is x_{r}. We define for r ∈ N, matrices A_{r} indexed by V × V, which generalize the adjacency matrix and which are polynomials in A.

(A_{r})_{xy} is the number of paths of length r with origin x, extremity y, without backtracking.

We should also note that A_{0} = Id and A_{1} = A= the adjacency matrix. The following lemma summarizes the relationship between A_{r} and A.

Lemma 3. 1. A_{1}^{2} = A_{2} + k · Id.

2. For r ≥ 2, A_{1}A_{r} = A_{r}A_{1} = A_{r+1} + (k − 1)A_{r−1}.

□

From the previous lemma, we can compute the generating function of the A_{r}’s.

Lemma 4. ∑_{r=0}^{∞} A_{r}t^{r} = \frac{1−t^{2}}{1−At+(k−1)t^{2}} .

□

To get rid of the 1 − t^{2} term in the numerator we will introduce new polynomials T_{m} in A given by:

T_{m} = ∑_{0≤r≤ \frac{m}{2}} A_{m−2r}

(m ∈ N).

Then the generating function of the T_{m}’s is

∑_{m=0}^{∞} T_{m}t^{m} = \frac{1}{1 − At + (k − 1)t^{2}} .  (4.11)

Definition. The Chebyshev polynomials of the second kind are defined by expressing \frac{sin(m+1)θ}{sin θ} as the polynomial of degree m in cos θ:

U_{m}(cos θ) = \frac{sin(m + 1)θ}{sin θ}, (m ∈ N).

For example U_{0}(x) = 1, U_{1}(x) = 2x, U_{2}(x) = 4x^{2} − 1, etc. Using trigonometric identities we can find the following recurrence relationship that the polynomials satisfy: U_{m+1}(x) = 2xU_{m}(x) − U_{m−1}(x). If we compute the generating function of the U_{m}’s we get ∑_{m=0}^{∞} U_{m}(x)t^{m} = \frac{1}{1−2xt+t^{2}} .

Performing a simple change of variables, we then compute the generating function of the related family of polynomials (k − 1)^{m/2}U_{m}(\frac{x}{2\sqrt{k−1}}) :

∑_{m=0}^{∞}(k − 1)^{m/2}U_{m}(\frac{x}{2\sqrt{k − 1}}) = \frac{1}{1 − xt + (k − 1)t^{2}} .  (4.12)

Comparing it with 4.11 we get the following expression for T_{m} as polynomials of degree m in the adjacency matrix.

Proposition 8. For m ∈ N, T_{m} = (k − 1)^{m/2}U_{m}(\frac{(A)_{xy}}{2\sqrt{k−1}}).

□

We are ready to do the trace estimates. We will do it in two different ways which will lead to the trace formula for X^{p,q}. By just considering the basis of the eigenfunctions we can write that

TrT_{m} = (k − 1)^{m/2} ∑_{j=0}^{n−1} U_{m}(\frac{μ_{j}}{2\sqrt{k − 1}})  (4.13)

On the other hand, by the definition of T_{m},

TrT_{m} = ∑_{0≤r≤m/2} T rA_{m−2r} = ∑_{x∈V} ∑_{0≤r≤m/2}(A_{m−2r})_{xx}  (4.14)

Definition. For x ∈ V, denote by f_{l,x} the number of paths of length l in X, without backtracking, with origin and extremity x; in other words f_{l,x} = (A_{l})_{xx}.

Hence by 4.13 and 4.14 we get the trace formula.

Theorem 12.

∑_{x∈V} ∑_{0≤r≤m/2} f_{m−2r,x} = (k − 1)^{m/2}U_{m} ∑_{j=0}^{n−1} U_{m}(\frac{μ_{j}}{2\sqrt{k − 1}}).  (4.15)
□

We should note that if the graph X is vertex transitive (i.e.for every pair of vertices x and y there exists α ∈ Aut(X) such that α(x) = y.), then the number f_{l,x} doesn’t depend on the vertex x, and we will denote it simply by f_{l}.

Corollary 2. In case of X^{p,q}, which is a vertex-transitive p + 1-regular graph, the trace formula takes the following form

∑_{0≤r≤m/2} f_{m−2r} = \frac{p^{m/2}}{n} U_{m} ∑_{j=0}^{n−1} U_{m}(\frac{μ_{j}}{2\sqrt{p}})  (4.16)

for every m ∈ N.

We will look at the left hand side of this trace formula in detail. For this, we introduce the quadratic form in 4 variables.

Q(x_{0}, x_{1}, x_{2}, x_{3}) = x_{0}^{2} + q^{2}(x_{1}^{2} + x_{2}^{2} + x_{3}^{2})  (4.17)

and for m ≥ 1, we set

s_{Q}(p^{m}) = {(x_{0}, x_{1}, x_{2}, x_{3}) ∈ Z^{4} : Q(x_{0}, x_{1}, x_{2}, x_{3}) = p^{m}, either x_{0} odd and x_{1}, x_{2}, x_{3} even, or x_{0} even and x_{1}, x_{2}, x_{3} odd}

Remark: Suppose either m is even or p = 1( mod 4). By reducing modulo 4, we see that in the above definition that all the 4-tuples (x_{0}, x_{1}, x_{2}, x_{3}) appearing have x_{0} odd and x_{1}, x_{2}, x_{3} even. So we introduce the quadratic form

Q′(x_{0}, x_{1}, x_{2}, x_{3}) = x_{0}^{2} + 4q^{2}(x_{1}^{2} + x_{2}^{2} + x_{3}^{2}).

Then s_{Q}(p^{m}) is exactly the number of integral representations of p^{m} by the quadratic form Q′.

Lemma 5. For m ∈ N s_{Q}(p^{m}) = 2 ∑_{0≤r≤ \frac{m}{2}} f_{m−2r}

Proof. We have proved that X^{p,q} is isomorphic to Y^{p,q}. We will identify X^{p,q} with Y^{p,q}. Let x_{0} = 1, x_{1}, …, x_{l−1}, x_{l} = 1 be the vertices of a path of length l, without backtracking, starting and ending at 1 in Y^{p,q}. Since Y^{p,q} is a Cayley graph we can find t_{1}, …, t_{l} ∈ T_{p,q} such that x_{i} = t_{1}t_{2} … t_{i} where i ≤ i ≤ l. We write t_{i} = π_{q}[α_{i}] for a unique α_{i} ∈ S_{p}. Then [α_{1}][α_{2}] … [α_{l}] is a reduced word of length l in Λ, since it is lifted from a path without backtracking. Because of the fact that π_{q}([α_{1}][α_{2}] … [α_{l}]) = x_{l} = 1, we see that [α_{1}][α_{2}] … [α_{l}] belongs to Λ(q) which is the ker(Λ(q)). This proves that f_{l} is the number of reduced words of length l in Λ belonging to Λ(q). Let (x_{0}, x_{1}, x_{2}, x_{3}) ∈ Z^{4} contribute to s_{Q}(p^{m}), so Q(x_{0}, x_{1}, x_{2}, x_{3}) = p^{m} and the correct congruences modulo 2 are satisfied. Let us form the quaternion α = x_{0} +q(x_{1}i+x_{2}j +x_{3}k). To complete the proof of Lemma 5, we need the following lemma.

Lemma 6. Λ(q) = {[α] ∈ Λ : α = a_{0} + a_{1}i + a_{2}j + a_{3}k, q|a_{1}, a_{2}, a_{3}}

Proof.

[α] ∈ Λ(q) ⇔ T_{q}(α) ∈ F_{q}^{×}
⇔ q doesn’t divide a_{0} and q|a_{1}, a_{2}, a_{3}
⇔ q|a_{1}, a_{2}, a_{3}

where the equivalence between the second and third lines follow from the fact that N(α) is a power of p and p ≠ q.

Let us go back to our α = x_{0} + q(x_{1}i + x_{2}j + x_{3}k). This α belongs to Λ′ and by the previous lemma its equivalence class is in Λ(q). From this we get

s_{Q}(p^{m}) = {α = a_{0} + a_{1}i + a_{2}j + a_{3}k ∈ Λ′ : N(α) = p^{m}, q|a_{1}, a_{2}, a_{3}}

By theorem 9, α has a unique factorization α = ±p^{l}w_{m−2l}, where w_{m−2l} is a reduced word of length m − 2l in Λ, and belongs to Λ(q). Conversely starting from a reduced word w of length m − 2l in Λ(q), the formula α = ±p^{l}w produces two quaternions as above. This shows that

|\{α ∈ Λ′ : N(α) = p^{m}, [α]| ∈ Λ(q)\} = 2 ∑_{0≤r≤ \frac{m}{2}} f_{m−2r}.

Hence the trace formula for X^{p,q} becomes, for every m ∈ N

s_{Q}(p^{m}) = \frac{2}{n}p^{\frac{m}{2}} ∑_{j=0}^{n−1} U_{m}(\frac{μ_{j}}{2\sqrt{p}}).  (4.18)

Now we will introduce the following subset Θ_{p} of ℂ, Θ_{p} = [i log \sqrt{p}, 0] ⋃[0, π] ⋃[π, π + i log p]. Recall that cos z = 1 − \frac{z^{2}}{2!} + \frac{z^{4}}{4!} − … = ∑_{n=0}^{∞}(−1)^{n} \frac{z^{2n}}{(2n)!} = \frac{e^{iz}+e^{−iz}}{2} . sin z = z − \frac{z^{3}}{3!} + \frac{z^{5}}{5!} − … = ∑_{n=0}^{∞}(−1)^{n} \frac{z^{2n+1}}{(2n+1)!} = \frac{e^{iz}+e^{−iz}}{2i}.

It is straight forward to check that the change of variables z ↦ 2\sqrt{p} cos z maps Θ_{p} bijectively to [−(p + 1), p + 1]; note that it maps [0, π] to [−2\sqrt{p}, 2\sqrt{p}], so this change of variables sees the Ramanujan interval. For j = 0, 1, …, n − 1 let θ_{j} ∈ Θ_{p} be the unique element of Θ_{p} such that μ_{j} = 2\sqrt{p} cos θ_{j}, i.e. θ_{j} ↔ 2\sqrt{p} cos θ_{j} by the change of variables. In particular θ_{0} = i log \sqrt{p} and if p is not a square modulo q then θ_{n−1} = π + i log \sqrt{p}. By the definition of the Chebyshev polynomial U_{m}, we have

s_{Q}(p^{m}) = \frac{2}{n}p^{\frac{m}{2}} ∑_{j=0}^{n−1} \frac{sin (m + 1)θ_{j}}{sin θ_{j}}  (4.19)

since U_{m}(\frac{μ_{j}}{2\sqrt{p}}) = U_{m}(\frac{2\sqrt{p} cos θ_{j}}{2\sqrt{p}}) = U_{m}(cos θ_{j})

To prove that X^{p,q} is Ramanujan, we therefore must prove that with the exception of θ_{0} and possibly of θ_{n−1}, all the θ_{j}’s are real. However in this paper we will only show that, for q sufficiently large, the imaginary part of θ_{j} is bounded above by a constant depending only on p. This will be enough to establish that the X^{p,q} form a family of expanders.

Since in the trace formula the θ_{j}’s are repeated according to the multiplicities of their corresponding eigenvalues we will state the following proposition without giving the proof, see [6], to have more information about these multiplicities.

Proposition 9. Let μ be a nontrivial eigenvalue of X^{p,q}, i.e. |μ| ≠ p + 1 and denote its multiplicity by M(μ). Then

M(μ) ≥ \frac{q − 1}{2}.

□

Theorem 13. Fix a real number ϵ with 0 < ϵ < \frac{1}{6}. For q ≥ p^{8}, every nontrivial eigenvalue μ of X^{p,q} satisfies

|μ| ≤ p^{5/6+ϵ} + p^{1/6−ϵ}  (4.20)

In particular the X^{p,q}’s are a family of expanders.

Proof. We start with our trace formula for X^{p,q}.

s_{Q}(p^{m}) = \frac{2}{n}p^{\frac{m}{2}} ∑_{j=0}^{n−1} \frac{sin (m + 1)θ_{j}}{sin θ_{j}}

for every m ∈ N. Here μ_{j} = 2\sqrt{p} cos θ_{j}. If μ_{j} is not in the Ramanujan interval [−2\sqrt{p}, 2\sqrt{p}], we write θ_{j} = iψ_{j} if 2\sqrt{p} < μ_{j} < p + 1 θ_{j} = π + iψ_{j} if −(p + 1) < μ_{j} < −2\sqrt{p} ,where 0 < ψ_{j} < log \sqrt{p}. From now on we assume that m is even. Recall that sinh z = \frac{e^{z}−e^{−z}}{2} = i sin(−iz) and cosh z = \frac{e^{z}+e^{−z}}{2} = cos(−iz). For μ_{j} not in [−2\sqrt{p}, 2\sqrt{p}] we have in both cases

\frac{sin (m + 1)θ_{j}}{sin θ_{j}} = \frac{sin (m + 1)ψ_{j}}{sin iψ_{j}} = \frac{sinh (m + 1)ψ_{j}}{sinh ψ_{j}} ≥ 0.

Then for a fixed nontrivial eigenvalue μ_{k} not in [−2\sqrt{p}, 2\sqrt{p}]:

s_{Q}(p^{m}) = \frac{2}{n}p^{\frac{m}{2}} M(μ_{k})\frac{sin (m + 1)ψ_{k}}{sin ψ_{k}} + \frac{2}{n}p^{\frac{m}{2}} ∑_{j:μ_{j}≠μ_{k}} \frac{sin (m + 1)θ_{j}}{sin θ_{j}}
≥ \frac{2}{n}p^{\frac{m}{2}} M(μ_{k})\frac{sinh (m + 1)ψ_{k}}{sinh ψ_{k}} + \frac{2}{n}p^{\frac{m}{2}} ∑_{j:|μ_{j}|≤2\sqrt{p}} \frac{sin (m + 1)θ_{j}}{sin θ_{j}} .

Using the fact that for θ real |\frac{sin(m+1)θ}{sin θ}| ≤ m + 1, we get

s_{Q}(p^{m}) ≥ \frac{2}{n}p^{\frac{m}{2}} M(μ_{k})\frac{sinh (m + 1)ψ_{k}}{sinh ψ_{k}} − 2p^{\frac{m}{2}} (m + 1).

We now estimate s_{Q}(p^{m}) from above. Since m is even s_{Q}(p^{m}) is the number of integral solutions of x_{0}^{2} + 4q^{2}(x_{1}^{2} + x_{2}^{2} + x_{3}^{2}) = p^{m}. We first estimate the number of possible choices for x_{0}. We have |x_{0}| ≤ p^{m/2}. Second, we have that x_{0}^{2} ≡ p^{m}( mod q^{2}), hence x_{0} ≡ ±p^{m/2}( mod q^{2}) since q ∤ x_{0}, q ∤ p. Since x_{0} and p are both odd, we have x_{0} ≡ ±p^{m/2}( mod 2q^{2}).

This gives at most 2(\frac{p^{m/2}}{q^{2}} + 1) choices for x_{0} since |x_{0}| ≤ p^{m/2}. Once x_{0} is fixed we must find the integral solutions to

x_{1}^{2} + x_{2}^{2} + x_{3}^{2} = \frac{p^{m} − x_{0}^{2}}{4q^{2}}

in integers.

Let us denote the number of different representations of n as a sum of three squares by r_{3}(n). Hence there are r_{3}(\frac{p^{m}−x_{0}^{2}}{4q^{2}} ) ways to solve the above equation.

Proposition 10. r_{3}(n) = O_{ϵ}(n^{\frac{1}{2} +ϵ}) for all ϵ > 0, i.e. there exists a constant C = C(ϵ) > 0 such that |r_{3}(n)| ≤ C(ϵ)n^{\frac{1}{2} +ϵ}.

□

r_{3}(\frac{p^{m} − x_{0}^{2}}{4q^{2}} ) ≤ C(ϵ)(\frac{p^{m} − x_{0}^{2}}{4q^{2}} )^{1/2+ϵ}
≤ C(ϵ)(\frac{p^{m}}{q^{2}} )^{1/2+ϵ}.

Hence

s_{Q}(p^{m}) ≤ C(ϵ)(\frac{p^{m}}{q^{2}} )^{1/2+ϵ}(\frac{p^{m/2}}{q^{2}} + 1) ≤ C(ϵ)(\frac{p^{m(1+ϵ)}}{q^{3}} + \frac{p^{m/2(1+2ϵ)}}{q}).

So far we have the lower and the upper bound for s_{Q}(p^{m}), that we can summarize with the following:

\frac{2}{n}M(μ_{k})\frac{sinh (m + 1)ψ_{k}}{sinh ψ_{k}} − 2p^{\frac{m}{2}} (m + 1) ≤ s_{Q}(p^{m}) ≤ C(ϵ)(\frac{p^{m(1+ϵ)}}{q^{3}} ) + (\frac{p^{m/2(1+2ϵ)}}{q}).

(4.21)

Hence

\frac{M(μ_{k})}{n}p^{\frac{m}{2}} \frac{sinh (m + 1)ψ_{k}}{sinh ψ_{k}} ≤ C(ϵ)(\frac{p^{m(1+ϵ)}}{q^{3}} ) + (\frac{p^{m/2(1+2ϵ)}}{q}).  (4.22)

Canceling out p^{\frac{m}{2}} and using n ≤ q^{3}, we get

M(μ_{k})\frac{sinh (m + 1)ψ_{k}}{sinh ψ_{k}} ≤ C(ϵ)[p^{m(1/2+ϵ)} + q^{2}p^{mϵ}] + q^{3}(m + 1).  (4.23)

Suppose that m is chosen in such a way that p^{\frac{m}{2}} ≤ q^{3}, which implies that m ≤ 6 log_{p} q. Then

M(μ_{k})\frac{sinh (m + 1)ψ_{k}}{sinh ψ_{k}} ≤ C(ϵ)[q^{3+6ϵ} + q^{2+6ϵ}] + q^{3}(1 + 6 log_{p} q).  (4.24)

Since ψ_{k} ≤ log \sqrt{p} ⇒ sinh ψ_{k} ≤ sinh log \sqrt{p} this yields:

M(μ_{k}) sinh(m + 1)ψ_{k} = O_{ϵ}(q^{3+6ϵ}).  (4.25)

Now take m to be the greatest even integer such that p^{\frac{m}{2}} ≤ q^{3}, which implies that m + 1 ≥ −1 + 6 log_{p} q. For q sufficiently large we have

sinh(m + 1)ψ_{k} = \frac{e^{(m+1)ψ_{k}} − e^{−(m+1)ψ_{k}}}{2}
≥ \frac{e^{(m+1)ψ_{k}}}{3}
≥ \frac{e^{(−1+6 log_{p} q)ψ_{k}}}{3}
≥ \frac{p^{−1/2}}{3} e^{6 log_{p} qψ_{k}}

where we used ψ_{k} ≤ log \sqrt{p} in the final inequality. Then

M(μ_{k}) = O_{ϵ}(q^{3+6ϵ− \frac{6ψ_{k}}{log p}}).  (4.26)

But, since μ_{k} is a nontrivial eigenvalue, we have

M(μ_{k}) ≥ \frac{q − 1}{2}

So for q large enough, we must have

3 + 6ϵ − \frac{6ψ_{k}}{log p} ≥ 1

giving

ψ_{k} ≤ (\frac{1}{3} + ϵ) log p

Then either θ_{k} = iψ_{k} or θ_{k} = π + iψ_{k}, and μ_{k} = 2\sqrt{p} cos θ_{k}, we get

|μ_{k}| = 2\sqrt{p}| cos(iψ_{k})| = 2\sqrt{p} cosh ψ_{k} ≤ p^{5/6+ϵ} + p^{1/6−ϵ},  (4.27)

for q big enough. This concludes the proof.

From theorem 12 and theorem 1 we immediately get estimates for the expanding constant of the graphs X^{p,q}.

Corollary 3. Fix 0 < ϵ < 1/6. For q sufficiently large, we have

h(X^{p,q}) ≥ \frac{p + 1 − p^{5/6+ϵ} − p^{1/6−ϵ}}{2} .  (4.28)

Hence X^{p,q}’s are families of expanders.

Example. To illustrate the construction of X^{p,q}, we directly worked out the following example.

Let p = 3 and q = 5. Since 3 is not a square modulo 5, we have X^{p,q} = X(PGL_{2}(F_{5}), S_{3,5}). By definition, PGL_{2}(F_{5}) = GL_{2}(F_{5})/ \{(\begin{matrix}λ & 0 \\ 0 & λ \end{matrix}) : λ ϵ F_{5}^{×}\}. Since |PGL_{2}(F_{q})| = q(q^{2} − 1), |PGL_{2}(F_{5})| = 120. For p = 3, q = 5, S_{p} equals the distinguished set of integral solutions of a_{0}^{2} + a_{1}^{2} + a_{2}^{2} + a_{3}^{2} = 3, namely

S_{p} = {s_{1} = i + j + k, s_{2} = −i + j + k, s_{3} = i − j + k, s_{4} = i + j − k}

Thus τ_{q}(S_{p}) = S_{p}. Using x = 2 and y = 0 in the definition of ψ_{q}, we find

ϕ(ψ_{q}(S_{p})) = \{[\begin{matrix}2 & 3 \\ 1 & −2 \end{matrix}] , [\begin{matrix}−2 & 3 \\ 1 & 2 \end{matrix}] , [\begin{matrix}2 & 1 \\ 3 & −2 \end{matrix}] , [\begin{matrix}2 & −1 \\ −3 & −2 \end{matrix}]\} ⊂ PGL_{2}(F_{5}),

By definition of the Cayley graph,

(A(X^{p,q}))_{i,j} = (A(X(PGL_{2}(F_{q}), S_{p,q})))_{i,j} ≠ 0 if and only if [A_{j}] = [A_{i}] · [s]

for some [s] ϵ ϕ(ψ_{q}(τ_{q}(S_{p}))).

After forming A(X^{p,q}) and calculating its eigenvalues by using computer program Matlab, we find that 4 and -4 are both eigenvalues with multiplicity 1. The degree of each vertex is 4, and there are no loops or multiple edges. Thus, X^{p,q} is a connected, 4-regular, simple graph. Furthermore, for every other non-trivial eigenvalue λ_{i}, we find |λ_{i}| ≤ 3 ≤ 2\sqrt{4 − 1}. Thus, the resulting graph is Ramanujan.

5. Zig-Zag Product

5.1. Motivation

In this section we present a recently invented method [2], [18] for giving explicit constructions of families of expanders, called the zig-zag product. We will analyze the expansion properties of the zig-zag product of two expander graphs and will see in detail the effect of taking the zig-zag product on the underlying graphs. The zig-zag product takes a large graph and a small graph and it produces a graph that inherits the size of the large, but the degree of the small one. This method solves our main problem, namely giving the explicit constructions of arbitrary large graphs with a small degree. The zig-zag product makes it possible to give an entirely combinatorial explicit construction of families of constant degree expander graphs. Hence starting with a constant size expander, one can apply successively the zig-zag product to obtain larger and larger expanders of the same fixed degree. So with less technology one can get expander graphs, which are however not Ramanujan. In this chapter we will allow graphs to have multiple edges and loops.

Definition. Let G be a k-regular graph on n vertices. The normalized adjacency matrix of G is Â = \frac{1}{k}A. We will denote its corresponding eigenvalues as follows:

μ′_{0} = 1 ≥ μ′_{1} ≥ … ≥ μ′_{n−1}

Definition. G is an [n, k, α]-expander if α is an upper bound on the absolute values of all nontrivial eigenvalues of the normalized adjacency matrix, that is |μ′_{i}| ≤ α for all i > 0.

Recall the lower bound \frac{k−μ_{1}}{2} ≤ h(G) in theorem 1. It also works with loops as we will see at the end of this chapter. Now μ′_{1} ≤ α implies that μ′_{1} · k ≤ α · k, hence μ_{1} ≤ α · k. So it follows from theorem 1 that [n, k, α]-expander satisfies

\frac{k(1 − α)}{2} = \frac{k − μ_{1}}{2} ≤ h(G)  (5.1)

and G is a better expander when α is closer to zero and is then (n, k, k(1 − α)/2)- expander.

In this section we will use two operations on the graphs: Squaring and the zig-zag graph product and look at the effect of these two operations on the three parameters, namely on n, k, α.

1.Squaring a graph

Definition. The square G^{2} = (V, E′) is a graph on the same vertices and (u, v) ∈ E′ if and only if there is a path of length two in G from u to v and there is one edge from u to v for each such path.

Note that if A is the adjacency matrix of G then A^{2} is the adjacency matrix of G^{2}. Moreover G^{2} is an [n, k^{2}, α^{2}]-expander, if G is [n, k, α]-expander.

Let us look at an example to clarify the above fact.

Example. :

Figure 5.1. [3, 2, 1/2]-expander

Above we have a 2-regular graph on 3 vertices. Let us denote it by G. The adjacency matrix of G is

A = [\begin{matrix}0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix}]

The characteristic polynomial of A is (x − 2)(x + 1)^{2}, hence the eigenvalues are

μ_{0} = 2 > μ_{1} = μ_{2} = −1

Since G is 2-regular

μ′_{0} = 1 > μ′_{1} = μ′_{2} = −1/2

Therefore G is an [3, 2, α]-expander where 1/2 ≤ α Now let us look at the graph G^{2}.

Figure 5.2. [3, 4, 1/4]-expander

We have in Figure 5.2 two loops on u, v, w since we have a path of length two from u to itself by going u → v , v → u and u → w, w → u. The same is true for v and w. And the edges between (u, v), (v, w) and (w, u) come from the path of length two u → w, w → v, v → u, u → w, w → v, v → u, respectively. Hence G^{2} is a 4-regular graph on 3 vertices. The adjacency matrix of G^{2} is

A^{∗} = [\begin{matrix}2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{matrix}]

Hence A^{∗} = A^{2}. The characteristic polynomial of A^{∗} is (x − 4)(x − 1)^{2}. So the eigenvalues of A^{∗} are

μ_{0} = 4 > μ_{1} = μ_{2} = 1

Since G^{2} is 4-regular

μ′_{0} = 1 > μ′_{1} = μ′_{2} = 1/4

Therefore G^{2} is an [3, 4, α^{2}]-expander where 1/2 ≤ α ⇒ 1/4 ≤ α^{2}.

2.Zig-zag graph product

We will define below the zig-zag graph product G ⋊ H of two graphs G and H and prove the following zig-zag theorem.

Theorem 14. Let G be an [n, m, α]-expander and H be an [m, d, β]-expander. Then G ⋊ H is an [nm, d^{2}, α + β + β^{2}]-expander.

Before we proceed with the definition let us show how it can be used for an explicit construction of a family of expanders with constant degree.

For some d, let H be a [d^{4}, d, 1/5]-expander. There exists such H by probabilistic argument and it can be found by exhaustive search for example. H will serve as a building block of our construction and we will define a sequence of graphs G_{n} as follows:

G_{1} = H^{2}  (5.2)
G_{n+1} = G_{n}^{2} ⋊ H  (5.3)

From the two facts, namely the properties of squaring and zig-zag graph product that we discussed above we can conclude that this sequence is indeed an infinite family of expanders.

Proposition 11. G_{n} is an [d^{4n}, d^{2}, 2/5]-expander for all n.

Proof. We will prove it by induction on n. Now G_{1} is an [d^{4}, d_{2}, 1/25]-expander, so it is an [d^{4}, d^{2}, 2/5]-expander. If we assume the statement for n then G_{n}^{2} is an [d^{4n}, d^{4}, 4/25]-expander and from the zig-zag theorem it follows that (G_{n}^{2})⋊H = G_{n+1} is an [d^{4n+4}, d^{2}, 4/25 + 1/5 + 1/25] = [d^{4n+4}, d^{2}, 2/5]-expander which concludes the proof.

Note that G_{n} will have in general multiple edges and loops. Let G_{n}^{s} be its simple graph obtained by dropping these. Since G_{n} is d^{2}-regular

h(G_{n}^{s}) > h(G_{n})/d^{2}

G_{n}^{s} will not be d^{2}-regular but the maximum degree of the vertices will be bounded above by d^{2} and it is an expander family in the earlier sense.

5.2. The construction and the proof of the zig-zag theorem

Let G be an [n, m, α]-expander and H be an [m, d, β]-expander. We will denote the vertices of G by u, v, .. etc. and we regard the vertices of H as the integers 1, 2, …, m. To obtain G ⋊ H, we replace every vertex v with a cloud of m vertices (v, 1), (v, 2), …, (v, m) one for every edge connected. The vertices within a cloud are connected by mini-edges so that every cloud forms a mini copy of H. The edges of G are augmented on both sides by these mini-edges to form the edges of G ⋊ H, i.e. at each vertex we will label the edges of G coming out each vertex with 1, 2, …, m and we will use this labeling to find the edges of G ⋊ H. Two vertices (v, k) and (u, l) are adjacent, if we can travel between them in a ‘zig-zag’ path of length three:

1. A step on H in the v-cloud

2. A step between the clouds, i.e. switching to the u-cloud according to an edge of G

3. Final step in the u-cloud.

Note that it is essential for the sake of well-definedness that the degree of G equals the size of H.

To make the above definition clear we will illustrate an example.

Example. :

Figure 5.3. G = [3, 2, 1/2]-expander

Let G to be a 2-regular graph on 3 vertices (see Figure 5.3). We have shown that it is an [3, 2, α]-expander where α ≥ 1/2. And let H to be a 2-regular graph on 2 vertices (see Figure 5.4). The adjacency matrix of H is

H = [\begin{matrix}1 & 1 \\ 1 & 1 \end{matrix}]

Hence the eigenvalues of H are μ_{0} = 2 > μ_{1} = 0. Since H is 2-regular μ′_{0} = 1 > μ′_{1} = 0. So H is an [2, 2, 0]-expander, where β ≥ 0.

Figure 5.4. H = [2, 2, 0]-expander

Now to construct the G ⋊ H, we have to follow the 3 steps to find the edges of our new zig-zag graph product. According to the first step we have to make a step on H. Let us start with the u-cloud. In the u-cloud we have two vertices labeled (u, 1), (u, 2). Let us find the edges going out from (u, 1). We have two options. Either we go from (u, 1) to (u, 1) or we go from (u, 1) to (u, 2). To complete the edges of G ⋊ H we have to take every possible step. Suppose we go from (u, 1) to (u, 1). Now we have to make a step between the clouds according to the edge labeling of G. Since we are at (u, 1) by Figure 5.3, the edge labeled with 1 in the u-cloud sends us to the v-cloud and to the vertex (v, 2). The final step is a step inside the v-cloud, where we have again two choices. So (u, 1) is connected in the zig-zag graph product to (v, 1) and (v, 2). Without giving the details let us summarize what happens if we start with (u, 1) and take the first step to (u, 2). 1)(u, 1) → (u, 2) 2)(u, 2) → (w, 1) 3)(w, 1) → (w, 1) or (w, 1) → (w, 2) Hence the total number of edges coming out from (u, 1) is 4 and its neighbors are (v, 1), (v, 2), (w, 1), (w, 2). If we do that for all the other edges we get the following graph for G ⋊ H.

Figure 5.5. G ⋊ H = [6, 4, 1/2]-expander The adjacency matrix M of G ⋊ H is:

M = [\begin{matrix}0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 \end{matrix}]

And the eigenvalues of M̂ = 1/4M are:

μ′_{0} = 1 > μ′_{1} = μ′_{2} = μ′_{3} = 0 > μ′_{4} = μ′_{5} = −1/2

Note that | − 1/2| = 1/2 + 0 + 0^{2}. We will introduce two matrices G̃ and H̃ in the proof of theorem 14 and use the fact that M = H̃G̃H̃, where this product stands for the three steps that we introduced to get the zig-zag product. For our example

G̃ = [\begin{matrix}0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{matrix}]

and

H̃ = [\begin{matrix}1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \end{matrix}]

It can be verified easily that M = H̃G̃H̃.

Let us look at another more interesting example, where we get multiple edges if we take the zigzag product of two graphs.

Example.: We will take the same G as in the previous example, namely [3, 2, 1/2]- expander. Let H be the following:

Figure 5.6. G ⋊ H = [6, 4, 1/2]-expander

Note that the adjacency matix of H is

H = [\begin{matrix}2 & 1 \\ 1 & 2 \end{matrix}]

And the eigenvalues of Ĥ = H/3 are 1 and 1/3, hence H is a [2, 3, 1/3]-expander. We will go through the same steps to find G ⋊ H. According to the zig-zag theorem the graph G ⋊ H will have 6 vertices and regularity 9. We will only show for one vertex namely (u, 1) how we find its neighbors and one can apply the same steps to the other vertices to complete the graph.

(u, 1) → (u, 1) → (v, 2) → (v, 2)

Since we have a double loop on (v, 1) and we have to take every possible step inside clouds we can take the second loop from (v, 2) to (v, 2) itself and we will have

(u, 1) → (u, 1) → (v, 2) → (v, 2)

And also since there are double loops on (u, 1) we get the same to edges taking the step from (u, 1) to (u, 1) by using the second loop. Hence there will be 4 edges in total connecting (u, 1) to (v, 2). Or we can have

(u, 1) → (u, 2) → (w, 1) → (w, 1)

which will appear again twice because of the loop on (w, 1). And finally

(u, 1) → (u, 2) → (w, 1) → (w, 2)

So in total we will have 9 edges going out form (u, 1), namely 4 connecting(u, 1) to (v, 2), 2 connecting (u, 1) to (v, 1), 2 connecting (u, 1) to (w, 1) and 1 connceting (u, 1) to (w, 2). Doing the same for every vertex we get the following graph:

Figure 5.7. G ⋊ H = [6, 9, 0.62284]-expander

The adjacency matrix of G ⋊ H is

M = [\begin{matrix}0 & 0 & 2 & 4 & 2 & 1 \\ 0 & 0 & 1 & 2 & 4 & 2 \\ 2 & 1 & 0 & 0 & 2 & 4 \\ 4 & 2 & 0 & 0 & 1 & 2 \\ 2 & 4 & 2 & 1 & 0 & 0 \\ 1 & 2 & 4 & 2 & 0 & 0 \end{matrix}]

The eigenvalues of M̂ = M/9 are

−0.62284, −0.62284, −0.1111, −0.1784, 0.1784, 1.

So G ⋊ H is [6,9,0.62284]-expander. Note that

1/2 + 1/3 + 1/3^{2} = 0.9444 > 0.62284.

G̃ is the same as in the previous example and

H̃ = [\begin{matrix}2 & 1 & 0 & 0 & 0 & 0 \\ 1 & 2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 1 & 0 & 0 \\ 0 & 0 & 1 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 & 1 \\ 0 & 0 & 0 & 0 & 1 & 2 \end{matrix}]

One can check that M = H̃G̃H̃.

Now we can give the formal definition of the zig-zag graph product.

Definition. Let G be an [n, m, α]-expander and H be an [m, d, β]-expander. For every vertex v ∈ V (G) let e_{v}^{1}, e_{v}^{2}, …, e_{v}^{m} be the edges connected to the vertex v of G. Regard the vertices of H as the integers 1, 2, …, m and denote it by [m]. G ⋊ H will have the vertex set V (G) × [m], and the edge set E′, where ((v, i), (u, j)) ∈ E′ iff there are some k, l ∈ [m] such that (i, k), (l, j) ∈ E(H)

1) e_{v}^{k} = e_{u}^{l},

2) there is an edge for each such k and l.

We now prove the theorem 14. To prove this zig-zag theorem we need the following proposition [18], which is also known as the Rayleigh quotient proposition.

Proposition 12. Let A be a real symmetric matrix with λ_{1} ≥ λ_{2} ≥ … ≥ λ_{n} be its absolute values of eigenvalues(possibly with multiplicities) then

λ_{1} = max_{∥x∥=1} |xAx^{T} |, …, λ_{n} = max_{∥x∥=1,x⊥x_{1},...,x_{n−1}} |xAx^{T} |  (5.4)

where x_{i} is an eigenvector corresponding to λ_{i}.

□

The proof is easy from looking at the action of A on expansion with respect to orthogonal basis of eigenvectors. We get similar formulas for μ_{i} if we drop the absolute values.

Corollary 4. If M is the normalized adjacency matrix of k-regular graph G with n vertices then the largest absolute value of the non-trivial eigenvalues of M is

λ = max_{ω⊥1_{n}} \frac{|⟨ω, Mω⟩|}{⟨ω, ω⟩} = max_{ω⊥1_{n}} \frac{∥Mω∥}{∥ω∥}  (5.5)

where ⟨., .⟩ refers to the standard inner product in R^{n} and ∥ω∥ = \sqrt{⟨ω, ω⟩} and 1_{n} is the n-vector with all entries 1.

□

Proof. We have to show that G ⋊ H is a [nm, d^{2}, α + β + β^{2}]-expander. The size nm and the degree d^{2} follows directly from the construction. We have to prove that

λ ≤ α + β + β^{2}  (5.6)

where λ is as in the corollary for M corresponding G⋊H. According to the definition we must show that for every vector ω ∈ R^{nm} such that ω⊥1_{nm} we have the property that |⟨Mω, ω⟩| is smaller than ⟨ω, ω⟩ by a factor α + β + β^{2}. For every vertex v (v between 1 and n) in G let us define ω_{v} ∈ R^{m} by (ω_{v})_{k} = ω_{vk} and a linear map C: R^{nm} → R^{n} by (Cω)_{v} = ∑_{k=1}^{m} ω_{vk}. Every ω_{v} can be decomposed uniquely into ω_{v} = ω_{v}^{∥} + ω_{v}^{⊥} where ω_{v}^{∥} is parallel to 1_{m}, i.e. all its entries are the same and ω_{v}^{⊥} is orthogonal to 1_{m}, i.e. the sum of its entries are zero. Thus we obtain a decomposition of ω:

ω = ∑_{v} e_{v} ⊗ ω_{v} = ∑_{v} e_{v} ⊗ ω_{v}^{∥} + ∑_{v} e_{v} ⊗ ω_{v}^{⊥} =_{def} ω^{∥} + ω^{⊥}  (5.7)

Note that ω^{∥} = Cω ⊗ 1_{m}/m. Since ω and ω^{⊥} are both orthogonal to 1_{nm}, so is ω^{∥} and hence also Cω is also orthogonal to 1_{n}. We have discussed that we follow three steps to get the zig-zag product G ⋊ H, namely a step from (v, i) to (v, k) in a cloud, a step from (v, k) to (u, l) and another step from (u, l) to (u, j). Therefore we will decompose M into the product of three matrices, corresponding to the three steps. Hence M = H̃G̃H̃, where H̃ = I_{n} ⊗ Ĥ is the matrix of a step in each cloud, Ĥ is the normalized adjacency matrix of H and

G̃_{(v,k),(u,l)} = \{ \begin{matrix}1 & if e_{v}^{k} = e_{u}^{l}; \\ 0 & otherwise. \end{matrix} \}

Note that G̃ is a permutation matrix and the relationship between G̃ and the adjacency matrix Ĝ of G, will be described later. Recall that it suffices to show that

\frac{|⟨Mω, ω⟩|}{⟨ω, ω⟩} ≤ α + β + β^{2}  (5.8)

for every w ∈ R^{nm}. By the symmetry of H̃, we have

|⟨H̃G̃H̃ω, ω⟩| = |⟨G̃H̃ω, H̃ω⟩|  (5.9)

Claim 4. H̃ω^{∥} = ω^{∥}.

Proof. We know that ω^{∥} = Cω ⊗ 1_{m}/m, H̃ = I_{n} ⊗ Ĥ and Ĥ1_{m} = 1_{m} since Ĥ is the normalized adjacency matrix of H and 1_{m} is the eigenvector with eigenvalue 1. Hence H̃ω^{∥} = (I_{n} ⊗ Ĥ)(Cω ⊗ 1_{m}/m) = (I_{n}Cω ⊗ Ĥ1_{m})/m = Cω ⊗ 1_{m}/m = ω^{∥}.

Hence H̃ω = H̃(ω^{∥} + ω^{⊥}) = ω^{∥} + H̃ω^{⊥}. Substituting this into 5.8 we have

⟨Mω, ω⟩ = ⟨G̃(ω^{∥} + H̃ω^{⊥}), ω^{∥} + H̃ω^{⊥}⟩  (5.10)

Using the inner product properties and the fact that G̃ is a permutation matrix we get

|⟨Mω, ω⟩| ≤ |⟨G̃ω^{∥}, ω^{∥}⟩| + 2∥ω^{∥}∥∥H̃ω^{⊥}∥ + ∥H̃ω^{⊥}∥^{2}  (5.11)

Now we will apply the expansion properties of G and H to bound each of these terms.

Claim 5. ∥H̃ω^{⊥}∥ ≤ β∥ω^{⊥}∥

Proof. H̃ω^{⊥} = H̃(∑_{v} e_{v} ⊗ ω_{v}^{⊥}) = (I_{n} ⊗ H)(∑_{v} e_{v} ⊗ ω_{v}^{⊥}) = ∑_{v} e_{v} ⊗ Hω_{v}^{⊥}. Since ∥Ĥω_{v}^{⊥}∥ ≤ β∥ω_{v}^{⊥}∥ for all v, ∥H̃ω^{⊥}∥ ≤ β∥ω^{⊥}∥.

Claim 6. |⟨G̃ω^{∥}, ω^{∥}⟩| ≤ α⟨ω^{∥}, ω^{∥}⟩.

Proof. The relationship between G̃ and the adjacency matrix Ĝ of G can be derived using the following formula: CG̃(e_{v} ⊗ 1_{m}/m) = Ĝe_{v} for all v in G. Since e_{v}’s form a basis this formula extends to all vectors γ ∈ R_{n} and we get CG̃(γ ⊗ 1_{m}/m) = Ĝγ. If we apply this formula to ω^{∥} = Cω ⊗ 1_{m}/m we get

CG̃ω^{∥} = CG̃(Cω ⊗ 1_{m}/m) = ĜCω  (5.12)

Thus

⟨G̃ω^{∥}, ω^{∥}⟩ = ⟨G̃ω^{∥}, Cω ⊗ 1_{m}⟩/m = ⟨CG̃ω^{∥}, Cω⟩/m = ⟨ĜCω, Cω⟩/m  (5.13)

Note that Cω is orthogonal to 1_{n}. Hence by the expansion property of G we know that ⟨ĜCω, Cω⟩/m ≤ α⟨Cω, Cω⟩/m. So

|⟨G̃ω^{∥}, ω^{∥}⟩| ≤ α⟨Cω, Cω⟩/m = α⟨Cω ⊗ 1_{m}, Cω ⊗ 1_{m}⟩/m^{2} = α⟨ω^{∥}, ω^{∥}⟩ (5.14)

Substituting the bounds of claim 5 and 6 into 5.10 we have

|⟨Mω, ω⟩| ≤ α∥ω^{∥}∥^{2} + 2β∥ω^{∥}∥∥ω^{⊥}∥ + β^{2}∥ω^{⊥}∥^{2}  (5.15)

Let p = \frac{∥ω^{∥}∥}{∥ω∥} and q = \frac{∥ω^{⊥}∥}{∥ω∥} such that p^{2} + q^{2} = 1. Then

\frac{|⟨Mω, ω⟩|}{⟨ω, ω⟩} ≤ αp^{2} + 2βpq + β^{2}q^{2} ≤ α + β + β^{2}  (5.16)

We finish this chapter by showing, as promised, how the lower bound h(G) ≥ (k − μ_{1})/2 in theorem 1, works even for graphs with loops. The proof here is obtained by modifying the proof in Wigderson’s lecture notes on his webpage. This modification allows us to drop the ‘without loops’ hypothesis that he has there.

Proof. Let G be a k-regular, connected graph G(V, E) on n vertices. We want to prove μ_{1} ≥ k − 2h(G). We will produce vector x⊥1_{n} such that \frac{xAx^{T}}{∥x∥} ≥ k − 2h(G). Fix S such that h(G) = |∂S|/|S|. Put S̄ = V − S. Let |S| = s and |S̄| = s̄. Let x = (\underbrace{s̄, …, s̄}_{s}, \underbrace{−s, …, −s}_{s̄}) where, without loss of generality, we number the vertices so that the first s are in S. Then x⊥1_{n} as x · 1_{n} = 0. Now ∥x∥^{2} = s̄^{2}s + s^{2}s̄ = ss̄(s + s̄) = nss̄.

For F ⊂ V let E(F), L(F) denote number of edges from vertices in F to other vertices in F and number of loops at vertices in F respectively. Then

xAx^{T} = (2|E(S)| + |L(S)|)s̄^{2} + (2|E(S̄)| + |L(S̄)|)s^{2} − 2ss̄|∂S|.  (5.17)

Since G is k-regular

ks = 2|E(S)| + |L(S)| + |∂(S)|, ks̄ = 2|E(S̄)| + |L(S̄)| + |∂(S)|.  (5.18)

Substituting 5.18 in 5.17 we get

xAx^{T} = nkss̄ − n^{2}|∂S|.

By Rayleigh quotient proposition,

μ_{1} ≥ \frac{xAx^{T}}{∥x∥^{2}} = k − \frac{n|∂S|}{ss̄} = k − \frac{nh(G)}{s̄} ≥ k − 2h(G),

since s̄ ≥ n/2.

6. Applications of Expanders

Expander graphs solve following interesting pure mathematics problems in various areas: in topology: expanding manifolds[9],[10], in group theory: generating random group elements[13], in measure theory: Ruziewicz problem[19] and F-spaces[11], in number theory: thin sets[1], etc. However it is also in applications in theoretical computer science where expanders have had their major impact. In this section we look at the applied ones. We cite a few such applications, as the design of the superefficient communication networks [4], constructions of error correcting codes with very efficient encoding and decoding algorithms [20], derandomization of random algorithms and its applications to cryptography [8], sorting and selecting rounds [17] and complexity theory [21].

We will explain briefly the problems and the use of expander graphs in each of the fields mentioned above.

Error Correcting Codes

The theory of error detecting and correcting codes is that branch of engineering and mathematics which deals with the reliable transmission and storage of data, see [20]. One of the most fundamental problems in communication is noise, that is when a message is transmitted over a channel, one can receive a slightly distorted version of the original message. Thus instead of sending a raw message of length m one sends the message with some additional redundant information of length n(the additional n − m digits are called check digits), so that the receiver can figure out the original message even if some errors occur. In a more formal way we can define a code to be an injective mapping from {0, 1}^{m} into {0, 1}^{n}. In place of message word w, f(w) is transmitted. The strings in the image of the mapping are called codewords. The length of the codewords, n, is called the block-length. The Hamming distance between two codewords is just the number of places in which they differ. One measure of the quality of a code is its minimum distance, which is the minimum of the Hamming distance between all pairs of codewords. Another measure is the relative minimum distance which is the minimum distance divided by n, where n grows large. The last parameter of a code we want to introduce is its rate m/n, which measures how much information is being transmitted with each bit. A linear code of block length n and rate r is a subspace of F_{2}^{n} of dimension rn, i.e. there are n − rn check digits and these are linear combinations of the rn message digits. Infinite families of error correcting codes are called asymptotically good if their rate and minimum distance remain constant as the block length grows. The goal of the study of errorcorrecting codes is to find codes of maximal minimum distance for their rate. While it is easy to show existence of good error-correcting codes, explicit constructions are more difficult. That is where we get help from explicit expander graphs. The codes whose construction depends on expander graphs are called expander codes. To construct an expander code we will use a linear code C of block length d, rate r and minimum distance δ and a d-regular expander graph G_{n} on n vertices. We will denote the expander code by C(G_{n}, C) and we will show that the expander code we construct has block length dn/2, rate 2r − 1 and minimum relative distance ≈ δ^{2}. We associate each edge in G with a bit of the code. So the length of the code is nd/2. For every vertex of G we make the restriction that the edges around the vertex form a codeword in C. This implies that there are (1 − r)d linear constraints on the bits of the linear code C, since C has rate r, where these constraints define a linear subspace of dimension rd. Then the total number of constraints in the entire graph G_{n} is (1 − r)nd. So we can choose nd/2 − (1 − r)nd = nd(r − 1/2) digits with freedom which gives actually the number of message digits. Hence the rate of the code C(G_{n}, C) is 2r − 1. Now we have to show that the expander code C(G_{n}, C) has the desired bound on its relative minimum distance. A convenient property that linear codes has is that the minimum distance between two codewords is equal to the minimum weight of a codeword, where the weight of a codeword is its distance from the all-0 word. We will use this property to find the bound on the minimum distance. The intuition is as follows: If the weight of a codeword is small then the weight of edges around some vertex is small which implies that the distance of C is small, which is obviously not the desired bound. However since our graph is an expander a small set of edges will touch many vertices which implies that the codewords doesn’t have low weights.

Lemma 7. (Alon-Chung) Let G be a d-regular graph on n vertices with second largest eigenvalue λ. Let X be a subset of the vertices of G of size αn. Then the number of edges contained in the subgraph induced by X in G is at most

(α^{2} + (α − α^{2})(λ/d))\frac{dn}{2}

edges.

□

According to this lemma one of these vertices touches at most d(α+(1−α)λ/d) of these edges as endpoints since there are αn vertices and every edge has 2 endpoints. But these should be at least δd for the code to be valid. So α + (1 − α)\frac{λ}{d} > δ, which implies that α > (δ − \frac{λ}{d})/(1 − \frac{λ}{d}). Hence the minimum distance is at least α(α + (1 − α)\frac{λ}{d} ∼ δ^{2}.

These codes are asymptotically good codes with linear decoding time which means that the running time increases linearly with the size of the input.

Derandomization of random algorithms and its applications to cryptography

A central problem in cryptography is that of relating various basic concepts such as one way function, pseudorandom generators and showing that they are equivalent, see [8].

Informally, a function f is a one-way function if 1. The description of f is publicly known and does not require any secret infor-

mation for its operation.

2. Given x, it is easy to compute f(x).

3. Given y, in the range of f, it is hard to find an x such that f(x) = y. More precisely, any efficient algorithm succeeds in inverting f with negligible probability.

So one uses f to encode, knowing f(x) and f, where it is hard to get x, unless you know more secret keys. To amplify the security of one-wayness, one uses iteration mixed with randomization. To reach the desired randomization constructive expanders are used where their explicit constructions allow us to perform a random walk on the expander. The idea is to associate the domain of the one-way function with the vertex set of the expander and randomize in each of the function by taking a random step on an expander. The main principal is that random walk on expander is rapidly mixing.

Sorting and selecting rounds

Best explicit sorting and selecting algorithms follow from the explicit expanders, where one identifies vertices of the expanders with the list elements and compare the list elements in rounds if corresponding vertices are joined by edges, see [17].

Complexity Theory

The complexity theory is the theory of classifying problems based on how difficult they are to solve. One model of solving is using logical circuits as in computer chips. Using expanders as circuits one can get results on bounds for number of gates to compute the linear transformations over finite fields, see [21].

References

[1] Miklós Ajtai, Henryk Iwaniec, János Komlós, János Pintz, and Endre Szemerédi, Construction of a thin set with small Fourier coefficients, Bull. London Math. Soc. 22 (1990), no. 6, 583–590. MR MR1099009 (92e:11010)

[2] Noga Alon, Alexander Lubotzky, and Avi Wigderson, Semi-direct product in groups and zig-zag product in graphs: connections and applications (extended abstract), 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), IEEE Computer Soc., Los Alamitos, CA, 2001, pp. 630–637. MR 1 948 752

[3] Noga Alon and Yuval Roichman, Random Cayley graphs and expanders, Random Structures Algorithms 5 (1994), no. 2, 271–284. MR 94k:05132

[4] Frédéric Bien, Constructions of telephone networks by group representations, Notices Amer. Math. Soc. 36 (1989), no. 1, 5–22. MR 90a:90052

[5] F. R. K. Chung, Diameters and eigenvalues, J. Amer. Math. Soc. 2 (1989), no. 2, 187–196. MR MR965008 (89k:05070)

[6] Giuliana Davidoff, Peter Sarnak, and Alain Valette, Elementary number theory, group theory, and Ramanujan graphs, London Mathematical Society Student Texts, vol. 55, Cambridge University Press, Cambridge, 2003. MR 2004f:11001

[7] Joel Friedman, A proof of alon’s second eigenvalue conjecture and related problems, Accepted to the Memoirs of the AMS (2004).

[8] Oded Goldreich, Russell Impagliazzo, Leonid Levin, Ramarathnam Venkatesan, and David Zuckerman, Security preserving amplification of hardness, 31st Annual Symposium on Foundations of Computer Science, Vol. I, II (St. Louis, MO, 1990), IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, pp. 318–326. MR 92k:94017

[9] M. Gromov, Random walk in random groups, Geom. Funct. Anal. 13 (2003), no. 1, 73–146. MR MR1978492 (2004j:20088a)

[10] Misha Gromov, Spaces and questions, Geom. Funct. Anal. (2000), no. Special Volume, Part I, 118–161, GAFA 2000 (Tel Aviv, 1999). MR MR1826251 (2002e:53056)

[11] N. J. Kalton and James W. Roberts, Uniformly exhaustive submeasures and nearly additive set functions, Trans. Amer. Math. Soc. 278 (1983), no. 2, 803– 816. MR MR701524 (85f:28006)

[12] Wen-Ch’ing Winnie Li, Character sums and abelian Ramanujan graphs, J. Number Theory 41 (1992), no. 2, 199–217, With an appendix by Ke Qin Feng and the author. MR MR1164798 (93h:11092)

[13] Alexander Lubotzky and Igor Pak, The product replacement algorithm and Kazhdan’s property (T), J. Amer. Math. Soc. 14 (2001), no. 2, 347–363 (electronic). MR MR1815215 (2003d:60012)

[14] M. Ram Murty, Ramanujan graphs, J. Ramanujan Math. Soc. 18 (2003), no. 1, 33–52. MR MR1966527 (2004d:11092)

[15] A. Nilli, On the second eigenvalue of a graph, Discrete Math. 91 (1991), no. 2, 207–210. MR 92j:05124

[16] M. Pinsker, On the complexity of a concentrator, 7 th international teletraffic conference (1973), 318/1–318/4.

[17] Nicholas Pippenger, Sorting and selecting in rounds, SIAM J. Comput. 16 (1987), no. 6, 1032–1038. MR MR917039 (89h:68019)

[18] Omer Reingold, Salil Vadhan, and Avi Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders, Ann. of Math. (2) 155 (2002), no. 1, 157–187. MR 2003c:05145

[19] Peter Sarnak, Some applications of modular forms, Cambridge Tracts in Mathematics, vol. 99, Cambridge University Press, Cambridge, 1990. MR MR1102679 (92k:11045)

[20] Michael Sipser and Daniel A. Spielman, Expander codes, IEEE Trans. Inform. Theory 42 (1996), no. 6, part 1, 1710–1722, Codes and complexity. MR 98d:94031

[21] Leslie G. Valiant, Graph-theoretic arguments in low-level complexity, Mathematical foundations of computer science (Proc. Sixth Sympos., Tatranská Lomnica, 1977), Springer, Berlin, 1977, pp. 162–176. Lecture Notes in Comput. Sci., Vol.

53. MR 58 #32067