24 ноября (четверг), 17:00, ауд.615 ИППИ РАН.
Андрей Купавский (EPFL, МФТИ)
Верхние и нижние оценки размера эпсилон-сетей
Пусть дано множество [n] из n элементов и некоторое семейство подмножеств этого множества. Подножество X в [n] называется эпсилон-сетью, если любое множество из семейства размера больше эпсилон n пересекается с X. В этом докладе я расскажу про последние результаты, касающиеся размера минимальных эпсилон-сетей для различных систем множеств. В частности, речь пойдет о верхней оценке Чана и др., основанной на так называемой shallow cell complexity, и о нижних оценках размера эпсилон-сетей для семейств множеств, заданных геометрически.
| 22.11.2016 | |