Андрей Михайлович Райгородский

Задачи о покрытии и размерность Вапника–Червоненкиса в комбинаторной геометрии и геометрии чисел

А.М.Райгородский планирует провести 4 занятия.

Занятие 1.: Вот пример типичной задачи о "покрытии".
В группе студентов и школьников, посещающих курс А.М. Райгородского в Дубне, 20 человек. Из них пять человек одинаково хорошо и лучше всех остальных решают задачи по комбинаторике, семь — по геометрии, шесть — по теории чисел и т.д. Нужно составить из этих молодых людей команду для участия в олимпиаде, чтобы в ней по каждому предмету нашелся специалист и чтобы ее размер был как можно меньше. На занятии проблема будет сформулирована в общем виде. Предполагается обсудить и доказать ряд красивых комбинаторных утверждений, позволяющих оценивать мощность так называемой системы общих представителей для совокупности подмножеств конечного множества или, как еще говорят, для гиперграфа.
Занятие 2.: На этом занятии будет рассказано об одном очень важном понятии, которое лежит на стыке комбинаторики, геометрии и теории вероятностей. Это понятие размерности Вапника–Червоненкиса. Окажется, что с его помощью удается решать многие комбинаторно-геометрические задачи о покрытии. В частности, речь пойдет о так называемых ε-сетях, являющихся своего рода геометрическими аналогами комбинаторных систем общих представителей.
Занятие 3.: На третьем занятии будет продолжено обсуждение многочисленных приложений комбинаторных задач о покрытии в геометрии. Здесь особое внимание будет уделено задаче о хроматическом числе пространства (т.е. о минимальном количестве цветов, в которые можно так покрасить все точки пространства, чтобы между одноцветными точками не было расстояния 1), проблеме Борсука о разбиении ограниченных множеств на части меньшего диаметра и проблеме Грюнбаума о покрытии ограниченных множеств шарами.
Занятие 4.: На этом занятии мы поговорим о некоторых задачах геометрии чисел, которая является важным разделом современной теории чисел. Основным ее объектом служит так называемая решетка на плоскости или в пространстве произвольной размерности. Одно из классических утверждений геометрии чисел принадлежит Минковскому: если выпуклая фигура на плоскости симметрична относительно начала координат и ее площадь больше четырех, то фигура содержит нетривиальную точку с целыми координатами. Здесь в роли решетки выступает множество целых точек на плоскости. На занятии мы увидим, что многие глубокие задачи геометрии чисел также могут быть решены с помощью теорем о покрытии.