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) )
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) |