Tata Institute of Fundamental Research
Independent Sets in $K_3^n$
Student Seminar
Speaker:
Girish Varma
Organiser:
John Barretto
Date:
Friday, 8 Nov 2013, 16:00 to 17:30
Venue:
D-405 (D-Block Seminar Room)
(Scan to add to calendar)
Abstract:
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)
| Speaker: | Girish Varma |
| Organiser: | John Barretto |
| Date: | Friday, 8 Nov 2013, 16:00 to 17:30 |
| Venue: | D-405 (D-Block Seminar Room) |
(Scan to add to calendar)
Abstract:
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)
Ref: Graph Products, Fourier Analysis and Spectral Techniques by Alon, Dinur, Friedgut, Sudakov (http://link.springer.com/article/10.1007%2Fs00039-004-0478-3)