Transcript Expander

Expanders
Presented by Alon Levin
29.10.2006
1
Expander - Intuitive Definition
Expander graph is an undirected graph:




Without “bottlenecks”
With high connectivity
With a “large” minimal cut
With “large” edge expansion
2
Expanders and their
applications







Computational Complexity Theory
Economical Robust Networks (Computer
Network, Phone Network)
Construction of Hash Functions
Error Correcting Codes
Extractors
Pseudorandom Generators
Sorting Networks
3
Expander – Definition via Edge
Expansion

The edge expansion of a graph G=(V,E) is :
min | E ( S , S ) |
 (G) 
|V |
S V ,|S |
|S|
2
Theorem:  d  1,   0, {G } ,
0
n n 1
Gn are d-regular.
 { Gn } is an explicit expander family.

 (Gn )  0 ,
4
Expanders – Definition via
Spectral Gap



We shall discuss undirected d-regular graphs from
now and on
We shall adopt the notion of A = A(G) as G’s
adjacency matrix
Since A is a real symmetric nn matrix it has n real
eigenvalues:
d  1  2  ...  n


We will denote = max( |2|, |n|)
The spectral gap is defined as d- .
A 1  d 1
1  A 1  d
5
Expanders – Definition via
Spectral Gap

A d-regular graph G is an (n, d, )-expander if
 = max { |i|:1<i≤n } = max { |2(G)|, |n(G)| } and d>

If G is an (n, d, )-expander then
2(G)/2d ≤ d- ≤ 2(G)
 large expansion ~ large spectral gap!
* We will prove the inequality right after we show a
rather helpful characterization of 2(G)
6
Reminder – Euclidean Scalar
Product and Norm
 x, y  
n
 xi yi
n
2
x
i
x   x, x  
i 1
i 1
Cauchy–Schwarz inequality :  x, y   x  y
n
Proof: P( x)   (ai x  bi ) 2
i 1
n
n
n
 P  0   P  ( 2ai bi )  4 ai   bi 2
2
i 1

n
 aibi 
i 1
  x, y  
n
2
a
 i 
i 1
2
i 1
i 1
n
2
b
i 
i 1
x  y
7
Reminder – Triangle Inequality
The triangle inequality: x  y  x  y
Proof:
8
Rayleigh Quotient

The second largest eigenvalue  of a real symmetric matrix
can be computed this way:
n
{
v
}
Proof: Let i i 1
be an orthonormal basis of A’s eigenvectors,
where the ith vector corresponds to eigenvalue i(A).
“≤”: If we let x  v2 or x  vn then we would get |2| and
|n|, so the maximum is at least .
9
Rayleigh Quotient
(Proof continues):
n
“≥”: Denote an arbitrary x as  ai vi and since
i 1
n
 a1=0. Now Ax   ai i vi and since that:

x v1  0
i 1
=max{|i|:1<i≤n
}
10
Spectral gap and edge
expansion
Now we are ready to prove the following lemma:
 if G is an (n, d, )-expander then d- ≤ 2(G)
Proof: G=(V,E), |V|=n. Let SV, |S|≤n/2. We shall set a
vector x similar to S’s indicator, but so that <x, 1 >=0
and so by the Rayleigh quotient we have
 Ax, x    x
So, we will define:
2
S
S
xu   | S | xv | S |
u
v
11
Spectral gap and edge
expansion

As we can easily see, x is orthogonal to 1 since

We can also notice the equalities:

| S |  | S |  n ; (| S |  | S |) 2  | S |2 2 | S || S |  | S |2  n 2
x
2
 | S |2 | S |  | S || S |2  | S || S | n
12
Spectral gap and edge
expansion

By A’s definition, ( Ax )u
symmetric:
10010100010


( u ,v )E
xv , and since A is
X1
-
Xi
-
xn
13
Spectral gap and edge
expansion
Edges
originating in S
Cut in half due
to edges double
count
Cut edges
14
Spectral gap and edge
expansion

Which implies
since by our assumption ,
because
15
Regular Graph Union
Here we shall prove a simple lemma:
If G is a d-regular graph over the vertex set V, and H is a
d’-regular graph over the same vertices, then
G’ = GH = (V,E(G)  E(H)) is a d+d’-regular graph
such that (G’)  (G) + (H)
G'
x

1,
x

1

0,

(
G
')


A
x, x 
Proof: Take x s.t.
Then,  AG ' x, x    AG x, x    AH x, x    (G )   ( H )

AG’=AG+ AH
Since it’s a multigraph
(edge set is a multiset)
Rayleigh
quotient
16
The Final Expander Lemma
Let G=(V,E) be an (n, d, )-expander and FE.
Then the probability that a random walk which starts on
an edge from F will pass on an edge from F on it’s tth
step is

F
bounded by

Motivation: Showing that a random walk on a good
expander (large spectral gap) behaves similarly to
independent choice of random edges
17
The Final Expander Lemma
Proof: x is a vertices distribution vector s.t.
xv=Pr[Our walk starts at vertex v]
 The probability to reach vertex u at certain point is
 Pr[v is reached ]Pr[u is reached from v], thus Pr[u is reached from

( v ,u )E
x 'u 

( v ,u )E
v]=1/d
Since G is d-regular
xv
, where x is the current distribution and x’ is
d
the new one. By the definition of A=A(G) we can write
x’=Ax/d. We denote Ã=A/d, so x’=Ãx.
 After i steps, the distribution is x’=Ãix.
18
The Final Expander Lemma

P is the probability that an edge from F will be
traversed on the tth step.

Let yw be the number of edges from F incident on w
divided by d.

Then,
19
The Final Expander Lemma

Calculation of initial x: first step is picking an edge
from F and then one of it’s vertices, so for vertex v it’s
dyv is the number of edges from F
incident on v
20
The Final Expander Lemma

G is d-regular, thus each row in à sums to one.
1
xv 
n
If x is the uniform distribution on G, i.e.
,
then Ax  x . Since x is a probability function, it can
be decomposed into x  x  x  , where  x , x  0
since x and x are probability functions:

1  nx ;  1, x     1, x  x  
 Pr[start on v]  
vV

vV
1
 1 1  0
n
Then,
t 1
t 1
t 1 
t 1 
A xA x A x x A x
21
The Final Expander Lemma


When G is d-regular, each row in à sums to one, and
thus if xv  1 then Ax  x .
n
A more intuitive way of seeing this, other than algebra,
is considering a random walk with uniform
distribution on a d-regular graph:
1
d
1
n
1
n
1
n
1
d
1
n
1
d
1
n
1
n
22
The Final Expander Lemma

Hence,
t 1
A x x
Linearity of
scalar product
 x , x    x , x  x  
  x , x    x , x  
 0 x
2
23
The Final Expander Lemma
n
x
2
1 n 1
 2  2 
n n
i 1 n
Cauchy-Schwartz
inequality
x  x
(Ã)=(A)/d
+
Rayleigh quotient t-1 times
x
2

  x, x    x   x , x   x  
  x  , x     x , x  2  x , x   

x
2

x
2
2  0 
x 
x
24
The Final Expander Lemma


xv  1
Since xi are positive,

vV
vV
vV
Maximum is achieved when all edges incident to v are
in F, and in that case x  d
, so:
x
2
  xv2  max xv  xv  max xv 
v
2| F |
2| F |
P  A x, x 
d
t 1
25
The Lubotzky-Phillips-Sarnak
Expander

Take a prime p, let V=Zp{}. Define 0-1= 
and connect every vertex x to:

x+1
x-1
x-1

It’s a 3-regular graph with <3



26
The Margulis/Gaber-Galil
Expanders

Take V=ZnZn, so |V|=n2. Given v=(x,y)V
connect it to the following vertices:
(x+2y,y)
 (x,2x+y)
 (x,2x+y+1)
 (x+2y+1,y)
(all operations are done modulo n)
 This is an 8-regular graph with =52<8, so it’s
spectral gap is about 0.93

27
The End

Questions?
28