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

Экстремальные задачи комбинаторики и теории геометрических графов

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

Лекции будут посвящены одному из самых ярких разделов современной комбинаторики — теории геометрических графов. Основным объектом нашего исследования будет так называемый дистанционный граф (он же граф расстояний), вершины которого — это точки плоскости (или пространства более высокой размерности), а ребра — отрезки заданной длины. Этот объект весьма труден для исследования, и на многие — казалось бы, простые — вопросы о его свойствах нет окончательных ответов. Нас будут в первую очередь интересовать «экстремальные» характеристики графов расстояний. Среди них хроматическое число — минимальное количество цветов, в которые можно так покрасить вершины графа, чтобы вершины, соединенные ребром, были разноцветными; обхват — длина кратчайшего цикла в графе. Для отыскания этих характеристик мы познакомимся с основами линейно-алгебраического и вероятностного методов в комбинаторике. Кроме того, мы пронаблюдаем интересные связи между задачами комбинаторной геометрии и теории кодирования.

Бóльшая часть материала будет доступна старшеклассникам. Приблизительная структура лекций следующая.

Лекция 1. Определение дистанционного графа. Простейшие свойства: число ребер в случае плоскости и пространства, хроматические числа в маленьких размерностях и др. Обхват дистанционного графа. Клики (полные подграфы) в дистанционных графах.

Лекция 2. Задача о наибольшей мощности совокупности M = {M₁,…, M_s} подмножеств конечного множества с запретами на величины |M_i ∩ M_j| . Линейно-алгебраический метод. Хроматические числа дистанционных графов в растущей размерности.

Лекция 3. Некоторые идеи теории кодирования. Построение дистанционных графов, не содержащих клик заданного размера и имеющих большое хроматическое число. Большое хроматическое число и большой обхват.

Лекция 4. Вероятностный метод. Уточнение результатов третьей лекции.

Organization Committee e-mail:
dubna@mccme.ru