1550075568-C-Algebras_and_Finite-Dimensional_Approximations__Brown_

E. Groups and Graphs 473

We note that srxs-^1 = rs.x. The stabilizer of an edge (x, y) EE is rCx,y) =

rx nrY. Every group acts by left multiplication on its Cayley graph X(r, S);

note that this action is free (i.e., all stabilizers are trivial).

Expanders. In this section, we consider a finite connected graph X. For

each vertex x E V, the degree of x is defined as

v(x) = l{Y EV: (x, y) E E}I.

A graph X is said to be d-regular if v(x) = d for all x. We set lvl =

I::xEV v(x) = IEI and denote by L^2 (V, v) the weighted L^2 -space on V: For

functions f and g on V, we have

(!, g)v = ~ 1""" L.J v(x) f(x)g(x). -

xEV

We define L^2 (E) to be the L^2 -space on E with the uniform weight. One

defines the "differential operator" d: L^2 (V, v) -+ L^2 (E) by (df)(x, y) =

f(y) - f(x). Then the combinatorial Laplacian ~ = ~x is defined as the

positive operator d*d/2 on L^2 (V, v). One checks that

(~f, f)v = ~lldfll

2

= 2 l~I· L lf(x) - f(y)l

2

(x,y)EE

= l~I L L (lf(x)l

2

• f(y)f(x))
  xEV y; (x,y)EE

= ~ 1'"' L.J v(x)(f(x)-v(x)^1 """ L.J f(y))f(x). -

xEV y; (x,y)EE

It follows that
1
(~f)(x) = f(x) - v(x) L f(y).
y; (x,y)EE
Since the graph X is connected, eigenvectors of the eigenvalue zero are
constant functions. We denote by A1 = A1 (X) the first nonzero positive
eigenvalue of~-
Let 1i be a Hilbert space and f: V -+ 1i be a function. We view f
as an element of the Hilbert space L^2 (V, v) @ 1i. Here's a Poincare-type
inequality.

Lemma E.5. Let X be a finite connected graph. Then, for any map f from

the vertex set V into a Hilbert space 1i, we have

A;I~) L v(x)v(y)llf(x) - f(y)ll^2 = A1(X)(llflli2cv,v)®H - llmll~)

x,yEV