Sensitivity Conjecture - co udowodnił Hao Huang

Speaker(s)

Krzysztof Oleszkiewicz

Affiliation

Uniwersytet Warszawski

Date

Nov. 7, 2019, 12:15 p.m.

Room

room 3260

Seminar

Seminar of Probability Group

---

Omówiony zostanie dowód następującego twierdzenia, które przez lata było otwartą hipotezą. Niech A będzie podzbiorem kostki dyskretnej {-1,1}^n o tej własności, że każdy wierzchołek należący do A ma co najwyżej d sąsiadów należących do A (dwa wierzchołki kostki nazywamy sąsiadami, gdy różnią się dokładnie jedną współrzędną). Jeśli d^2<n, to do A należy co najwyżej połowa wierzchołków kostki.

---