на главную страницу ЛШСМ-2019 к списку курсов ЛШСМ-2019

Андрей Михайлович Райгородский

Раскраски гиперграфов

А. М. Райгородский планирует провести 2-3 занятия.

Я очень люблю рассказывать следующую задачу. «Есть 30 школьников. Из них выбрали пятерых лучших комбинаторщиков, пятерых лучших геометров, пятерых лучших числовиков и т.д. (всего 15 пятерок, каждая по своему предмету). Всегда ли можно так рассадить этих 30 школьников по двум аудиториям, чтобы в каждой аудитории был хотя бы один представитель каждой из пятерок?» Это прекрасная задача, связанная со многими замечательными вопросами современной комбинаторики, в том числе с открытыми! Но что будет, если дополнительно потребовать, чтобы в каждой аудитории оказалось «примерно поровну» представителей из каждой группы? Это делает задачу еще более красивой и нетривиальной. В такой постановке в ней есть и вероятностные аспекты, и связи с теорией кодирования, и связи с классической до сих пор нерешенной проблемой отыскания так называемых матриц Адамара.

Для понимания курса специальных предварительных знаний не требуется.