Transcript CayleyGraphs

Cayley Graphs & Expanders
Steve the presenter
Some history
Arthur Cayley
The Real Arthur Cayley
For more demoralizing facts,
visit his homepage on Wikipedia
• Son of a British
merchant in Russia
who wedded a Russian
girl.
• English Super Genius
• Did everything
• Very smart and knew
more than 6 languages
including yours and
math.
• Occupied Lucasian
Chair and fathered
British pure math
• Died at 74
Some Definitions
Let G be a graph (finite and infinite), and let S be a non-empty, finite
subset of G. Here we assume S to be symmetric, S = S −1
Definition: The Cayley graph G(G, S) is the graph with the vertex set
V = G and edge set
E = {{x,y} : x,y in G, there exist s in S : y = xs}
Hence, two vertices are adjacent if one is obtained from the other by
right multiplication by some element of S.
Note, since S is symmetric, this adjacency relation is also symmetric,
i.e, a ~ b implies b ~ a, so that the resulting graphs are undirected.
Cayley graphs are motivated by the Cayley Theorem, which
states hat every group G is isomorphic to a subgroup of the
symmetric group on G.
Let's look at some examples:
If G = Zn is the finite cyclic group of order n and the set S consists of
two elements, the standard generator of G and its inverse, then the
Cayley graph is the cycle Cn.
G = Z/6Z, S = {1, -1}
G = Z/6Z, S = {2, -2}
G = Z/6Z, S = {2, -2}
G = Z/6Z, S = {3}
G = Z/6Z, S = {3}
G = Z/6Z, S = {2, -2, 3}
G = Z/6Z, S = {2, -2, 3}
G = Sym(3), S = {(123), (132), (12)}
non-isomorphic groups, isomorphic Cayley Graphs
MOre Examples
Similarly, suppose now that G = Z is the infinite cyclic group and
the set S consists of the standard generator 1 and its inverse (−1 in
the additive notation) then the Cayley graph is an infinite chain.
G = Z, S = {1, -1}
G = Z, S = {1, -1}
This of course simply the number line.
G = Z, S = {2, -2, 3, -3}
G = Z , S = {(0,1), (-1,0), (0,1), (0,-1)}
2
G = L2, the free group on 2 generators a, b; S = {a, a-1, b, b-1}
Alternatively, if we draw each new edge horizontal and
vertical to half the length, this gives rise to fractal images.
The Cayley graphs of infinite groups provide interesting
geometries!
Expanders
Now what is an expander?
The investigation of an expander centres around the
following question:
Given a sparse set of points, how do we systematically
construct a highly connected yet efficient network between
the points?
Conceivably, the answer to such a question is of great
interest to electric grid constructors and designers of
network between computers among many others.
Cayley Graphs, Groups and expanders
In the previous slides, we have seen that Cayley
graphs give very nice encoding of the structure of
discrete groups.
Conversely, it also helps us sometimes to translate a
graph problem back into its group presentation. This
way, we can I will not tell you how now because I
don't know yet. But do remember to ask me about it if
you see me next semester!
Expanders
We consider graphs X = (V, E), where V again is the
set of vertices and E the set of edges of X. Here we
shall limit ourselves to the case that X is undirected
and finite.
A path in X is a sequence v1, v2,...., vk of vertices, where
vi is adjacent to vi+1 (i.e. and {vi, vi+1} is an edge).
A graph X is connected if every two vertices can be joined
by a path. (One can trace from one vertice to another one
through a series of edges.)
Finally a graph is k-regular if every vertex is also
connected to k other vertices through k-edges.
• This is the celebrated Petersen Graph.
• It is clearly connected.
• In fact, it is a 3-regular expander.
• Let F be a subset of V, The boundary ∂F is the the
set of edges connecting F to V – F.
• In our case here, F = 3, V – F = 7, ∂F are the seven
black “fat” edges.
• The expanding constant, or the isoperimetric
constant of X, is:
• h(X) = inf {abs(∂F)/(min{abs(F),abs(V – F)}) : F
is subset of V, 0 < abs(F) < +∞}
• h(X) = inf {abs(∂F)/(min{abs(F),abs(V – F)}) : F
is subset of V, 0 < abs(F) < +∞}
• If we view X as a network transmitting
information (where retained by some vertex
propagates, say in one unit of time, to neighboring
vertices), then h(X) measures the quality of X as a
network:
• h(X) is large, information propagates well.
Let's consider two extreme examples:
• The complete graph Km on m
vertices is defined s.t. Every
vertex is connected to one
another, e.g. m = 5.
• It's clear in this case, if F = i,
∂F = i(m-i) s.t. h(Km) = m/2
• The cycle Cn on n vertices:
• When n = 6, if F is a half-cycle,
∂F = 2
• h(Cn) is smaller than 2/(n/2) =
4/n
• In particular, h(Cn) goes to zero
as n goes to infinity
• Thus we see that highly connected complete graph
has a large expanding constant that grows
proportionately with the number of vertices.
• On the other hand, the minimally connected graph
has a small expanding constant that goes to zero as
n increases.
• In this sense, h(X) does indeed give us a measure
of the “quality” of the network.
That's all I know about expanders at this point.
Thank you!