Series: Mathematics Colloquium

Date: Thursday, February 20, 2003

Time: 4:30 - 5:30 PM

Place: 102 McAllister Building

Host: Ed Formanek

Refreshments: 4:00 - 4:30 PM, in 212 McAllister

Speaker: Martin Kassabov, Yale University

Title: Kazhdan Property and Finite Graphs

Abstract:

In this talk I survey several classical results about Kazhdan's
Property T and apply them to two combinatorial problems involving
finite graphs -- the construction of families of expanders and the
working time of product replacement algorithm in computational group
theory.  Kazhdan's property T originated from the representation
theory of Lie groups.  Shortly after its introduction it was used by
Margulis to construct an explicit example of a family of expanders.
Unfortunately, the expanding constant of this family was unknown,
because all proofs that a group has a property T were not
quantitative, and the expanding constants of this family of expanders
was unknown.  In a recent paper, A. Lubotzky and I. Pak showed that
Kazhdan property T of the group SL_n(Z) implies that the working time
of the product replacement algorithm on k-generated abelian groups is
logarithmic in the size of the groups, but its dependence on k was
unknown.  A recent result by Y. Shalom gave an explicit bound of the
Kazhdan constant for the group SL_n(Z), which lead to quantitative
bounds for the constants in these two combinatorial constructions.