На этом сайте будут публиковаться записки авторского курса по выбору на физтехе под условным названием “От комбинаторики к геометрии”. Я буду писать о (почти) элементарных сюжетах из комбинаторики, подчёркивая их некомбинаторные приложения. По своей сути, эти лекции будут повторять и развивать темы, которые я рассказывал на своих комбинаторных спецкурсах в 2014-2015 гг. Два глобальных сюжета, которые я надеюсь осветить за семестр, такие:

  1. от леммы Холла до двойственности линейного программирования;

  2. от леммы Шпернера до топологической степени отображения.

Если останется время, обсудим что-нибудь ещё.

Буду рад, если все интересующиеся запишутся в email-рассылку курса здесь. Это ни к чему не обязывает, но вы будете получать уведомления о том, что происходит с курсом.

Я всячески приветствую обратную связь и готов корректировать темы в зависимости от пожеланий читателей. Не стесняйтесь писать мне по любым вопросам на почту или оставлять анонимные комментарии в гугл-форме.

Я буду стараться писать доступно для первокурсников. С другой стороны, я не хочу, чтобы читателям постарше было скучно это читать, и постараюсь включать интерлюдии посложнее. Начнём мы с вещей, которые многие могли слышать на школьных олимпиадных кружках, но мы разгонимся достаточно быстро и дойдём до тем, которые не входят в стандартные физтеховские курсы.

Желающие могут получить (дифференцированный) зачёт по курсу. Для этого нужно присылать мне на почту (в любом виде) решения задач, которые будут публиковаться параллельно с лекциями. Надеюсь, что любители олимпиадных задач (и желающие готовиться к студенческим матолимпиадам) оценят их. Для оценки “отл 10” будет достаточно решить около половины из них. Официально в зачётку будет проставляться зачёт под универсальным названием “Современные приложения дискретной математики и функционального анализа”.

Ниже я привожу примерную программу.

Часть 1: выпуклая двойственность. Лемма Холла и вариации (теоремы Кёнига, Дилворта, Татта, Менгера, Фробениуса). Линейная релаксация задачи дискретного программирования. Теорема Эгервари. Теорема Биркгофа–фон Неймана в контексте выпуклой двойственности. Теорема Форда–Фалкерсона. Двойственность линейного программирования. Отделимость выпуклых множеств. Теорема Хана–Банаха.

Часть 2: топологическая степень отображения. Лемма Шпернера. Приложение к справедливому делению. Дискретные аналоги леммы Шпернера (hex-лемма, connector-лемма). Непрерывные аналоги леммы Шпернера (теорема Брауэра, теорема Кнастера–Куратовского–Мазуркевича). Приложение: причёсывание ежа. Топологическая размерность Лебега. Степень отображения. Лемма Такера и теорема Борсука–Улама. Задача о разрезании ожерелья.

(?) Части 3+: трюк Линдстрома–Гесселя–Вьенно? группы отражений и системы корней? теоремы типа Хелли?