Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




Большой семинар лаборатории комбинаторных и геометрических структур
1 апреля 2021 г. 19:00, Москва, Онлайн! https://zoom.us/j/279059822 пароль: первые шесть цифр числа \pi после запятой
 


Covering the hypercube with geometry and algebra

Yu. Wigderson
Дополнительные материалы:
Adobe PDF 114.1 Kb

Количество просмотров:
Эта страница:161
Материалы:23
Youtube:



Аннотация: What is the smallest number of hyperplanes needed to cover the vertices of the hypercube $\{0, 1\}^n$? At least two hyperplanes are needed, and since we may take the parallel hyperplanes $x_1=0$ and $x_1=1$, we see that two hyperplanes suffice.
Although the question above is not particularly interesting, there are many interesting variants of it, with connections to discrete geometry, infinite Ramsey theory, theoretical computer science, extremal combinatorics, and beyond. One such question is the following: how many hyperplanes are needed to cover all vertices of the hypercube except the origin, while not covering the origin? Here, Alon and Füredi proved that at least $n$ hyperplanes are needed, and it is easy to see that $n$ hyperplanes also suffice.
Although these problems are geometric in nature, all known proofs of the Alon–Füredi theorem use algebraic techniques, relating the hyperplane covering problem to a polynomial covering problem and then resolving this latter problem. Miraculously, the geometric problem and its algebraic relaxation turn out to have the same answer. In this talk, I will survey some results and questions about covers of the hypercube, and then discuss a recent result showing that for a natural higher-multiplicity version of the Alon–Füredi theorem proposed by Clifton and Huang, the geometric and algebraic problems (probably) have very different answers.
Joint work with Lisa Sauermann.

Дополнительные материалы: yuval_wigderson_bigsem.pdf (114.1 Kb)
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024