Independent Sets in $K_3^n$



Friday, 8 November 2013, 16:00 to 17:30


  • D-405 (D-Block Seminar Room)


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 (