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

Лекции будут посвящены одному из самых ярких разделов современной комбинаторики — теории геометрических графов. Основным объектом нашего исследования будет так называемый дистанционный граф (он же граф расстояний), вершины которого — это точки плоскости (или пространства более высокой размерности), а ребра — отрезки заданной длины. Этот объект весьма труден для исследования, и на многие — казалось бы, простые — вопросы о его свойствах нет окончательных ответов. Нас будут в первую очередь интересовать «экстремальные» характеристики графов расстояний. Среди них хроматическое число — минимальное количество цветов, в которые можно так покрасить вершины графа, чтобы вершины, соединенные ребром, были разноцветными; обхват — длина кратчайшего цикла в графе. Для отыскания этих характеристик мы познакомимся с основами линейно-алгебраического и вероятностного методов в комбинаторике. Кроме того, мы пронаблюдаем интересные связи между задачами комбинаторной геометрии и теории кодирования.
Бо́льшая часть материала будет доступна старшеклассникам. Приблизительная структура лекций следующая.
Лекция 1. Определение дистанционного графа. Простейшие свойства: число ребер в случае плоскости и пространства, хроматические числа в маленьких размерностях и др. Обхват дистанционного графа. Клики (полные подграфы) в дистанционных графах.
Лекция 2. Задача о наибольшей мощности совокупности $M=\{M_1,\dots,M_s\}$ подмножеств конечного множества с запретами на величины $|M_i\cap M_j|$. Линейно-алгебраический метод. Хроматические числа дистанционных графов в растущей размерности.
Лекция 3. Некоторые идеи теории кодирования. Построение дистанционных графов, не содержащих клик заданного размера и имеющих большое хроматическое число. Большое хроматическое число и большой обхват.
Лекция 4. Вероятностный метод. Уточнение результатов третьей лекции.