Ramanujan Graphs (The Best Expanders)

Ranveer (CSE, IIT Indore)

 Applications

Covers broad areas of mathematics and computer science.

1 Explicit construction of robust networks
2 Error correcting codes
3 Derandomization of random algorithms
4 Quantum cryptography
5 Analysis of algorithms in computational group theory
6 Sorting networks
7 Complexity theory
 Expanders

Graphs which are

1 Very sparse

2 Well-connected
 Sparse

Let G = (V , E ) be a graph on |V | = n nodes.

The number of edges |E | << O(n2 ).

3n
|E | = 2 , that is, O(n).
 Well-connected

Every subset of the vertices has large boundary.

 Brain graph

The human brain has about 1011 (one hundred billion) neurons.
Each neuron is connected to only 7,000 other neurons on an
average via synapses.
 Expansion ratio

The expansion ratio of a graph G = (V , E ) on n vertices is

|∂S|
h(G ) = min ,
S⊂V ,0<|S|≤ n2 |S|

where ∂S is the boundary of S, that is, the set of edges with

exactly one endpoint in S.

h(G ) is also known as the isoperimetric number or Cheeger

constant.
 Implication

The number of edges between a subset S and its complement S 0 is

at least h(G ) × min(|S|, |S 0 |).
 Examples

4
1 Cycle Cn on n vertices: h(Cn ) ≤ n → 0, as n → ∞.
n
2 Complete graph Kn on n vertices: h(Kn ) ∼ 2 → ∞, as
n → ∞.
3 Petersen graph: h(G ) = 1.

Petersen Graph

4 For connected graphs h(G ) > 0.

 Expander graphs

Definition: A family {Gn }, n = 1, 2, . . . , ∞, of d-regular graphs

and there exists  > 0 such that h(Gn ) ≥  for every n.

Family of cycle graphs (Cn ) and complete graphs (Kn ) are not
expander families.
 Intractable h(G )

No polynomial time algorithm to calculate h(G ).

Tomorrow if there is any polynomial time algorithm for h(G ), then

P=NP.

Hence, it will settle one among the seven millennium problem of

the world at present.

What to do??
 Alon, Milman, 1985
Let G be a connected d-regular graph on n vertices and
λ1 ≥ λ2 ≥ . . . ≥ λn be the eigenvalues of the adjacency matrix.
1 λ1 = d.
2 λn = −d iff G is bipartite graph.

Theorem1
d − λ2 p
≤ h(G ) ≤ 2d(d − λ2 )
2

Figure: From left: Noga Alon, Milman

1
Alon, N. and Milman, V.D., 1985. 1, isoperimetric inequalities for graphs,
and superconcentrators. Journal of Combinatorial Theory, Series B, 38(1),
pp.73-88.
 Spectral gap

Spectral gap: d − λ2 .
d − λ2 p
≤ h(G ) ≤ 2d(d − λ2 ).
2
Smaller λ2 is better.
 First explicit construction of expanders
Margulis, 1973

For every natural number m, consider G = (V , E ), where

V = Zm × Zm . Every vertex (x, y ) is connected to
(x ± y , y ), (x ± (y + 1), y ), (x, y ± x), and (x, y ± (x + 1)), where
the arithmetic is modulo m.

Fields Medal - 1978 (Postpone due to denial of Visa to Helsinki)

Abel Prize - 2020 (Postpone due to Covid-19)
 Example and analysis2

Z3

This construction yield family of 8-regular graphs with λ2 < 8.

2
Gabber, O. and Galil, Z., 1981. Explicit constructions of linear-sized
superconcentrators. Journal of Computer and System Sciences, 22(3),
pp.407-420.
 A slight variant

(x, y ) is connected to the vertices

(x ± 2y , y ), (x ± (2y + 1), y ), (x, y ± 2x), and (x, y ± (2x + 1)).

√
This variant yields a better known bound λ2 ≤ 5 2 ∼ 7.071.
 How better an expander family can be3
All sufficiently large d-regular graphs has
√
λ2 ≥ 2 d − 1 − on (1),

where on (1), is the term tending to 0 as n → ∞.

From left: Noga Alon, Ravi Bopanna

√
Let λ = max|λi |<d |λi |, i = 1, . . . , n. Also, λ ≥ 2 d − 1 − on (1).

3
Alon, N., 1986. Eigenvalues and expanders. Combinatorica, 6(2), pp.83-96.
 Ramanujan Graphs
The largest spectral gap
√
The d-regular graphs with λ ≤ 2 d − 1.
 Examples

λ = 2.818, h(G ) = 0.25

Other trivial examples

1 Complete graphs : λ = 1
2 Complete bipartite graphs : λ = 0
3 Petersen graph : λ = 2
Explicit construction of a family of Ramanujan graphs.

A challenge!!
 The first construction
LPS4

Morgenstern, Lubotzky-Phillips-Sarnak: d-regular Ramanujan

graphs exist when d − 1 is a prime power.

From left: Alex Lubotzky, Ralph S. Phillips, Peter Sarnak

It uses a Ramanujan conjecture hence they coined the name.

4
Lubotzky, A., Phillips, R. and Sarnak, P., 1988. Ramanujan graphs.
Combinatorica, 8(3), pp.261-277.
 LPS Example

An 6-regular Ramanujan graph.

 Random d-regular graphs
Friedman5

√
For d fixed and  > 0 the probability that λ ≤ 2 d − 1 +  tends
to 1 as n → ∞.

So a random d-regular graph is asymptotically Ramanujan.

5
Friedman, J., 2003. Relative expanders or weakly relatively Ramanujan
graphs. Duke Mathematical Journal, 118(1), pp.19-35.
 Expanders
2-Lift
Given a graph G = (V , E ), a 2-Lift of G is a graph Ĝ = (V̂ , Ê )
that has two vertices {v0 , v1 } ⊆ V̂ for each vertex v ∈ V . If (u, v )
is an edge in E , then E 0 can either contain the pair of edges

{(u0 , v0 ), (u1 , v1 )},

or
{(u0 , v1 ), (u1 , v0 )}.

v v0 v1 v0 v1

OR

u u0 u1 u0 u1

in G in Ĝ in Ĝ
 1

3
1 G 1

2 2

4 4

3 3

Duplicate every vertex

1

2
1

3
4
A 2-lift of G
3

Edges (1, 3), (2, 3) are crossed in Ĝ .

 More examples

A 3-D cube is a 2-lift of K4

The icosahedron graph is a 2-lift of K6

 1
1
2
1
2

4
4
3
4
3

 
0 1 1 1
1 0 1 0
A=
1

1 0 1
1 0 1 0
The eigenvalues of A are {2.56, 0, −1, −1.56}
 1
1
2
1
2

4
4
3
4
3

Signed adjacency matrix

 
0 1 −1 1
1 0 −1 0
As = 
−1 −1 0 1


1 0 1 0

The eigenvalues of As are {2, 1, −1, −2}

 The eigenvalues of 2-lifts

Old eigenvalues of Ĝ : σ(A) = {2.56, 0, −1, −1.56}.

New eigenvalues of Ĝ : σ(As ) = {2, 1, −1, −2}.
The eigenvalues of Ĝ : σ(Â) = {2.56, 2, 1, 0, −1, −1, −1.56, −2}.

Theorem: σ(Â) = σ(A) ∪ σ(As ) taken with multiplicities.

 Proof

The adjacency matrix of 2-lift can be written as

 
A A2
 = 1 . (1)
A2 A1

Note that, A = A1 + A2 , As = A1 − A2 . Suppose (α, v ), (β, u) be

eigenpairs of A, As , respectively. Then
 !  !
v u
α, , β,
v −u
   
v u
are eigenpairs of Â. As , are orthogonal, and they are 2n
v −u
in numbers, thus span all the eigenvectors of Â.
 Conjecture6

Bilu and Linial conjectured that every d-regular graph has a

signing√in which all of the new eigenvalues have absolute value at
most 2 d − 1.

From left: Nati, Bilu

For√every d-regular graph there is As with spectral radius

O( [Link] 3/2 d).

6
Bilu, Y. and Linial, N., 2006. Lifts, discrepancy and nearly optimal spectral
gap. Combinatorica, 26(5), pp.495-519.
 Infinite Bipartite Ramanujan graphs7
Srivastava-Marcus-Spielman proved the conjecture for d-regular
bipartite graphs.

Since the 2-lift of a bipartite graph is also bipartite, starting with a

d-regular complete bipartite and inductively forming the
appropriate 2-lifts gives an infinite sequence of d-regular bipartite
Ramanujan graphs.

7
Marcus, A.W., Spielman, D.A. and Srivastava, N., 2015. Interlacing
families I: Bipartite Ramanujan graphs of all degrees. Annals of Mathematics,
182, 307–325
 Continue..Open problem

Later Srivastava-Marcus-Spielman8 there exist bipartite Ramanujan

graphs of every degree and every number of vertices.

Michael B. Cohen9 showed how to construct these graphs in

polynomial time.

Open Problem: Are there exist infinitely many d-regular

non-bipartite Ramanujan graphs for any d ≥ 3?

8
Marcus, A.W., Spielman, D.A. and Srivastava, N., 2018. Interlacing
families IV: Bipartite Ramanujan graphs of all sizes. SIAM Journal on
Computing, 47(6), pp.2488-2509.
9
Cohen, M.B., 2016, October. Ramanujan graphs in polynomial time. In
2016 IEEE 57th Annual Symposium on Foundations of Computer Science
(FOCS) (pp. 276-281). IEEE.
 zig-zag product10
Define a (n, m)-graph as any m-regular graph on n vertices. Also,
[m] = {1, . . . , m}. Let G be an (n, m)-graph and H be an
(m, d)-graph. For every vertex v ∈ V (G ) we fix some numbering
ev1 , . . . , evm of the edges incident with v .
Definition: G H = (V (G ) × [m], E 0 ), where ((v , i), (u, j)) ∈ E 0
iff there are some k, l ∈ [m] such that (i, k), (l, j) ∈ E (H) and
evk = eul .

From left: Gold, Vadhan, Avi

10
O. Reingold, S. Vadhan, and A. Wigderson. Entropy waves, the zig-zag
graph product, and new constant-degree expanders. Annals of Mathematics
(2), 155(1):157–187, 2002.
 Example

G : Grid Z2 (left), H: 4-cycle (middle), G H (right)

Define a (n, d, λ)-graph as any d-regular graph on n vertices,

λ = max|λi |<d |λi |, i = 1, . . . , n.
Let G be (n, m, λ1 )-graph and H be (m, d, λ2 )-graph, then G H
is (nm, d 2 , f (λ1 , λ2 ))-graph, where f (λ1 , λ2 ) < λ1 + λ2 + λ22 .
 Other references used

1 Hoory, S., Linial, N. and Wigderson, A., 2006. Expander

graphs and their applications. Bulletin of the American
Mathematical Society, 43(4), pp.439-561.
2 Goldreich, O., 2011. Basic facts about expander graphs. In
Studies in Complexity and Cryptography. Miscellanea on the
Interplay between Randomness and Computation (pp.
451-464). Springer, Berlin, Heidelberg.
3 Sarnak, P.C., 2004. What is... an expander?. notices of the
American Mathematical Society, 51(7), pp.762-763.
4 Google images