Speaker: Eyal Rozenman (Hebrew University, Jerusalem)

Title:
------
"A New Explicit Construction of Constant-Degree Expander Cayley Graphs"

Abstract:
---------
Expander graphs are widely used in Computer Science and Mathematics. A
graph is expanding if the second eigenvalue of the standard random walk on
this graph is bounded away from 1 (equivalently, the smallest eigenvalue
of the Laplacian is strictly larger than 0).

Several explicit constructions of infinite families of constant degree
expanders are Cayley graphs, namely graphs defined by groups and
generators. All these constructions start with a single infinite "mother"
group, plus a special finite set of generators, and constructs the
infinite family by taking larger and rager finite quotients of the
"mother" group.

Recently, a new approach was introduced by Reingold et al (Annals '01) for
explicitely constructing expander graphs. This approach starts with a
single finite "seed" graph, and iteratively constructs larger and larger
graphs of the same constant degree, via a new graph product (called the
"zig-zag" product). They prove that if the "seed" graph is a good enough
expander, so are all graphs in the infinite family.

We prove a similar theorem for a family of Cayley graphs. However, in
contrast, the expansion of the "seed" graph in our family is an open
question (see below).The proof relies on the connection between zig-zag
product of graphs and semi-direct product in groups of Alon et al (FOCS
'01). The groups in the family are (essentially) the automorphism groups
of a k-regular tree of every finite depth ( very different than previously
used groups). The generators are constructed by efficient algorithms for
solving certain equations over the symmetric group (implicit in Nikolov
'02). An essential part is the analysis of the expansion of a Cayley graph
on two copies of a group GxG with (perfectly correlated) set of generators
of the form (g, g^{-1}), when all elements of G are commutators.

The main open problem is to prove the conjecture below, which would
establish the expansion of the "seed" Cayley graph (and hence by the
theorem of all others in the family).

Conjecture: For some finite k, there exists a set of k^{1/5} permutations
in S_k, such that the resulting Cayley graph is an expander.

No special backgroung will be assumed.

(Joint work with Avi Wigderson (IAS))