Семинар проводится совместно кафедрой дискретной математики ФИВТ МФТИ, кафедрой математических основ управления ФУПМ МФТИ и кафедрой высшей математики МФТИ.
На заседаниях семинара обсуждаются задачи современной комбинаторики, дискретной геометрии, теории кодирования, теории алгоритмов и др., а также их приложения.
Расписание семинаров доступно здесь.
На следующем семинаре 6 ноября состоится выступление Маргариты Ахмеджановой
"Онлайн раскраски гиперграфов"
В докладе будет рассказано об одной увлекательной задаче, связанной одновременно с теорией игр и раскрасками гиперграфов.
Рассмотрим следующую игру.
Можно легко доказать, что при N<2^n Remover имеет выйгрышную стратегию (http://www.ccs.neu.edu/home/jaa/papers/AslamDh93.pdf), а при N>8*2^n Pusher. В пару строк доказывается наличие стратегии у Pushera при N>n*2^n (https://arxiv.org/pdf/1506.01148.pdf). Теперь если рассмотреть другую задачу с 3 дорогами и Remover удаляет с 2 из 3 дорог, то есть только оценки 3^n и 4n*3^n (результат Хузиевой и Шабанова).
Рассмотрим следующую игру.
- Есть 2 игрока: Pusher и Remover, и есть 2 дороги, на каждой из которых отмечено n позиций: n, n-1,...,1, 0, 1, ...., n-1, n.
- В начале игры на каждой дороге стоит N фишек на позиции с номером n.
- Далее, в каждом раунде Pusher выбирает произвольное количество фишек на первой и второй дороге и сдвигает их на одну позицию вперед к 0. Remover после каждого хода Pushera удаляет все сдвинутые фишки в этом раунде, но только с одной дороги.
- Pusher выигрывает если хотя бы 1 фишка дошла до 0, Remover-если удалены все N фишек.
Можно легко доказать, что при N<2^n Remover имеет выйгрышную стратегию (http://www.ccs.neu.edu/home/jaa/papers/AslamDh93.pdf), а при N>8*2^n Pusher. В пару строк доказывается наличие стратегии у Pushera при N>n*2^n (https://arxiv.org/pdf/1506.01148.pdf). Теперь если рассмотреть другую задачу с 3 дорогами и Remover удаляет с 2 из 3 дорог, то есть только оценки 3^n и 4n*3^n (результат Хузиевой и Шабанова).
