speaker:           Benny Sudakov
            Princeton University and IAS

title: Graph Products, Fourier Analysis and Spectral Techniques

                           Abstract

Assume that at a given road junction there are $n$ three-position switches
that control the red-yellow-green position of the traffic light. You are
told that no matter what the switch configuration is, if you change the
position of every single one of the switches then the color of the light
changes. Is it true that in fact the light is controlled by only one of
the switches? What if the above information holds for only 99.99% of the
configurations? The above question deals with a special case of coloring a
graph which is a product of smaller complete graphs (in this case
cliques of size 3). In the talk I will present some results about
independent sets and colorings of product graphs, including stability
versions (see the "99.99%" question above.) Our approach is based on
Fourier analysis on Abelian groups and on Spectral Techniques.
Joint work with Alon, Dinur and Friedgut