Expander families and Cayley graphs. A beginner's guide by Krebs M., Shaheen A.

Show description

When doing this, we may think of an element f of L2 (X) in several different ways: (a) as a function; (b) as a picture, where we draw the graph X and label each vertex v ∈ V with the value of f at the vertex v, that is, with f (v); and (c) as a vector, where we give the vertices of V a particular ordering v1 , . . , vn and then think of f as the vector (f (v1 ), . . , f (vn ))t . We frequently use L2 (E) where E is the edge multiset of X. Here we think of f ∈ L2 (E) as a function on the edge multiset of X.

Then, |Bm | = m(n − 1)!. Note that α ∈ Bm and β ∈ Bm are adjacent if and only if β = αγ = α ◦ γ for some γ ∈ . We have three cases to consider. Throughout the cases, assume that α ∈ Bm , β ∈ Bm , and β = αγ . 1. Suppose γ = σ . Since α ∈ Bm , the permutation α cannot map any element between 1 and m to 1. To ensure that β ∈ Bm , we must have that α (m + 1) = 1. This implies that β (m) = 1. There are (n − 1)! such β . We get one edge from σ that leaves Bm for each such β . 2. If γ = σ −1 , then we must have that α (n) = 1 and β (1) = 1.

THE LAPLACIAN The adjacency operator is one of the many linear operators associated to a graph. In this section, we discuss another one, called the Laplacian. Recall from multivariable calculus that the ordinary Laplacian is defined by (f ) = div(grad(f )) and that it provides a measure of a function’s rate of change. The Laplacian on a graph is a discrete analogue. There are several reasons for introducing this new operator. One is that the results in this section simplify the proofs of many of our main theorems.