Группы подстановок и проблема изоморфизма графов - Васильев Андрей Викторович. Лекция 3

«Математическая весна» – ежегодная студенческая школа-конференция, проводимая в Нижнем Новгороде Лектор:Васильев Андрей Викторович, лаборатория алгебры Института математики им. С.Л. Соболева СО РАН, Новосибирск Проблема изоморфизма графов состоит в нахождении наиболее эффективного алгоритма проверки изоморфизма конечных графов. Несмотря на значительные усилия многих математиков в последние 50 лет, время работы лучших из предложенных алгоритмов остается по существу экспоненциальным. Прорывом в этой области стал недавний результат Л. Бабаи, предлагающий квазиполиномиальный алгоритм проверки изоморфизма графов. Основные составляющие этого алгоритма: теория конечных групп подстановок, многомерные когерентные конфигурации и алгоритмы Лакса и Вейсфейлера – Лемана. В лекциях мы расскажем об алгоритме Вейсфейлера - Лемана, шуровых когерентных конфигурациях, а также их группах автоморфизмов, которые являются замыканиями групп подстановок Обсудим связь проблемы нахождения таких замыканий и проблемы изоморфизма графов, а также поговорим о других близких вопросах, в частности, о проблеме изоморфизма групп. #математическая_весна #ВШЭ #математика #теория_графов #теория_групп