School of Technology and Computer Science Seminars

Independent Sets in $K_3^n$

by Mr. Girish Varma (School of Technology and Computer Science, TIFR)

Friday, November 8, 2013 from to (Asia/Kolkata)
at Colaba Campus ( D-405 (D-Block Seminar Room) )
Description
We will prove the following fact: Assume that there are n three position switches that control whether the  color of a single bulb is red, green or yellow. You are told that whenever you change the position of all the switches then the color of the light changes. Prove that in fact the bulb is controlled by only one of the switches.

Ref: Graph Products, Fourier Analysis and Spectral Techniques by Alon, Dinur, Friedgut, Sudakov (http://link.springer.com/article/10.1007%2Fs00039-004-0478-3)