Abstract:
Пусть дано множество [n] из n элементов и некоторое семейство подмножеств этого множества. Подножество X в [n] называется эпсилон-сетью, если любое множество из семейства размера больше эпсилон n пересекается с X. В этом докладе я расскажу про последние результаты, касающиеся размера минимальных эпсилон-сетей для различных систем множеств. В частности, речь пойдет о верхней оценке Чана и др., основанной на так называемой shallow cell complexity, и о нижних оценках размера эпсилон-сетей для семейств множеств, заданных геометрически.
|
