Title: Coloring products of graphs, a Fourier approach

Speaker: Ehud Friedgut, Hebrew University, Jerusalem

Date: February 11, 2003, 4:30-5:30

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

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. Can you prove 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 k_3^n). In the talk I will present some results about independent sets and colorings of such graphs, including stability versions (see the "99.99%" question above.) Our approach is based on Fourier analysis on Abelian groups. This is joint work with Irit Dinur.