Jin-Yi Cai(University of Wisconsin, Madison):
Some geometric descriptions of an expander construction
Some time ago I gave a series talks on a construction of a family of
constant degree expander graphs, starting from every unimodular matrix B
which is not elliptic. The construction is a generalization of the
Gabber-Galil construction, and is based on combinatorial properties of B and
analytic estimates such as Parseval's equality. The construction finally boils
down to collecting a set of lattice points in the "neighborhood" set
N_B ={q \in Z^2 | \mu[UB \cap U_q]\not = 0 }
where \mu is the Lebesgue measure, U is the unit square, UB is the image
of U under B, and U_q is the shifted copy of U by vector q.
In this talk, I will give a direct geometric descriptions of this
"neighborhood" construction. In particular I will give an exact value of
the size of this "neighborhood" set, which becomes an exact bound on the
degree of the family of expander graphs. It is shown that the number of
lattice points in this set is one less than the sum of the absolute value of
the elements of the matrix B.