Задача о раскрасках. Андрей Райгородский.
✨ «Математика добра»: благотворительная конференция продолжается! Можно ли рассадить 30 школьников по двум кабинетам так, чтобы в каждом оказался хотя бы один представитель каждой из 15 «пятёрок лучших»? И почему ответ на этот простой вопрос приводит к одной из главных нерешённых задач современной комбинаторики? О чём эта лекция? Лекция посвящена классическим задачам комбинаторики и теории графов, связанным с понятием раскраски. Начнём с простой «затравочной» задачи про школьников и кабинеты — и постепенно доберёмся до знаменитой проблемы Эрдёша–Хайнала о хроматическом числе гиперграфов. Увидим, как вероятностный метод позволяет доказать существование объектов, не предъявляя их явно, и как жадные алгоритмы помогают строить оптимальные раскраски. Это не лекция про гипотезу четырёх красок — но задачи, о которых пойдёт речь, находятся в самом центре современной дискретной математики. Кто спикер? Андрей Михайлович Райгородский — доктор физико-математических наук, директор Физтех-школы прикладной математики и информатики МФТИ, профессор МФТИ и МГУ. Руководитель совместных исследовательских программ Яндекса и МФТИ, заведующий лабораторией продвинутой комбинаторики и сетевых приложений. Лауреат премии Президента РФ в области науки и инноваций для молодых учёных (2011). Автор более 200 научных статей и 20 учебников и монографий. Организатор школ «Комбинаторика и алгоритмы» и математических программ в «Сириусе». Один из главных популяризаторов комбинаторики в России. Кому будет полезно? Старшеклассникам и студентам младших курсов, олимпиадникам, всем, кто интересуется комбинаторикой и теорией графов. Для понимания основных идей достаточно знакомства с числами сочетаний и базовым определением графа — всё остальное будет объяснено по ходу лекции. Смотреть можно бесплатно на YouTube, а если есть возможность — направьте донейшен в фонд, который выбрал лектор: деньги уходят напрямую, без комиссии, и любая сумма — это реальная помощь. А в благодарность мы даём бонусы — и, честно, самое ценное чувство: «в эти каникулы я помог(ла)». Все подробности, программа конференции и как присоединиться: https://www.notion.so/mathloversclub/2025-2ce28c0e851781988268f5d5e99fb141 И подпишитесь на наш Telegram-канал с анонсами следующих лекций и напоминаниями: https://t.me/mathloversclub28/ Частые запросы: раскраска графов, хроматическое число, теория графов, гиперграфы, комбинаторика, задача Эрдёша, вероятностный метод, олимпиадная математика, Райгородский лекция, дискретная математика. Sapere aude! #математика #комбинаторика #теорияграфов #раскраски #олимпиады #математикадобра
✨ «Математика добра»: благотворительная конференция продолжается! Можно ли рассадить 30 школьников по двум кабинетам так, чтобы в каждом оказался хотя бы один представитель каждой из 15 «пятёрок лучших»? И почему ответ на этот простой вопрос приводит к одной из главных нерешённых задач современной комбинаторики? О чём эта лекция? Лекция посвящена классическим задачам комбинаторики и теории графов, связанным с понятием раскраски. Начнём с простой «затравочной» задачи про школьников и кабинеты — и постепенно доберёмся до знаменитой проблемы Эрдёша–Хайнала о хроматическом числе гиперграфов. Увидим, как вероятностный метод позволяет доказать существование объектов, не предъявляя их явно, и как жадные алгоритмы помогают строить оптимальные раскраски. Это не лекция про гипотезу четырёх красок — но задачи, о которых пойдёт речь, находятся в самом центре современной дискретной математики. Кто спикер? Андрей Михайлович Райгородский — доктор физико-математических наук, директор Физтех-школы прикладной математики и информатики МФТИ, профессор МФТИ и МГУ. Руководитель совместных исследовательских программ Яндекса и МФТИ, заведующий лабораторией продвинутой комбинаторики и сетевых приложений. Лауреат премии Президента РФ в области науки и инноваций для молодых учёных (2011). Автор более 200 научных статей и 20 учебников и монографий. Организатор школ «Комбинаторика и алгоритмы» и математических программ в «Сириусе». Один из главных популяризаторов комбинаторики в России. Кому будет полезно? Старшеклассникам и студентам младших курсов, олимпиадникам, всем, кто интересуется комбинаторикой и теорией графов. Для понимания основных идей достаточно знакомства с числами сочетаний и базовым определением графа — всё остальное будет объяснено по ходу лекции. Смотреть можно бесплатно на YouTube, а если есть возможность — направьте донейшен в фонд, который выбрал лектор: деньги уходят напрямую, без комиссии, и любая сумма — это реальная помощь. А в благодарность мы даём бонусы — и, честно, самое ценное чувство: «в эти каникулы я помог(ла)». Все подробности, программа конференции и как присоединиться: https://www.notion.so/mathloversclub/2025-2ce28c0e851781988268f5d5e99fb141 И подпишитесь на наш Telegram-канал с анонсами следующих лекций и напоминаниями: https://t.me/mathloversclub28/ Частые запросы: раскраска графов, хроматическое число, теория графов, гиперграфы, комбинаторика, задача Эрдёша, вероятностный метод, олимпиадная математика, Райгородский лекция, дискретная математика. Sapere aude! #математика #комбинаторика #теорияграфов #раскраски #олимпиады #математикадобра