Задача о раскрасках. Андрей Райгородский⁠⁠

Для тех, у кого сложности с ютубом - дублируем на вк.видео:

🔍 О чём эта лекция? Лекция посвящена классическим задачам комбинаторики и теории графов, связанным с понятием раскраски. Начнём с простой «затравочной» задачи про школьников и кабинеты — и постепенно доберёмся до знаменитой проблемы Эрдёша–Хайнала о хроматическом числе гиперграфов. Увидим, как вероятностный метод позволяет доказать существование объектов, не предъявляя их явно, и как жадные алгоритмы помогают строить оптимальные раскраски. Это не лекция про гипотезу четырёх красок — но задачи, о которых пойдёт речь, находятся в самом центре современной дискретной математики.

👨‍🏫 Кто спикер? Андрей Михайлович Райгородский — доктор физико-математических наук, директор Физтех-школы прикладной математики и информатики МФТИ, профессор МФТИ и МГУ. Руководитель совместных исследовательских программ Яндекса и МФТИ, заведующий лабораторией продвинутой комбинаторики и сетевых приложений. Лауреат премии Президента РФ в области науки и инноваций для молодых учёных (2011). Автор более 200 научных статей и 20 учебников и монографий. Организатор школ «Комбинаторика и алгоритмы» и математических программ в «Сириусе». Один из главных популяризаторов комбинаторики в России.

😏 Кому будет полезно? Старшеклассникам и студентам младших курсов, олимпиадникам, всем, кто интересуется комбинаторикой и теорией графов. Для понимания основных идей достаточно знакомства с числами сочетаний и базовым определением графа — всё остальное будет объяснено по ходу лекции.

Полезные ссылки:

📅 Расписание конференции: https://www.notion.so/mathloversclub/2025-2ce28c0e851781988268f5d5e99fb141

📺 YouTube-канал (трансляции лекций): https://www.youtube.com/@mathloversclub

💬 Telegram-канал (анонсы и новости): https://t.me/mathloversclub28

🔔 Бот для напоминаний о лекциях: https://t.me/matematika_dobra_bot

⭐ Boosty - записи лекций для тех, у кого не работает YouTube: https://boosty.to/mathloversclub