Вторник, 23 сентября, zoom. Начало в 15:00.
Докладчик: И.Н. Пономаренко (ПОМИ).
Тема: Большое семейство сильно регулярных графов с малой размерностью Вейсфейлера-Лемана.
Abstract
В 2002 году Д. Фон-дер-Флаассом было предложено семейство сильно регулярных графов, отличающееся большим количеством/разнообразием элементов (prolific family). В этом докладе мы обсудим, что такое сильно регулярные графы и как строятся подобные конструкции. Мы покажем, что для бесконечного числа натуральных чисел $n$ семейство Фон-дер-Флаасса содержит $n^{\mathsf{\Omega}(n^{2/3})}$ сильно регулярных $n$-вершинных графов $X$ с одинаковыми параметрами и удовлетворяющих следующему условию: изоморфизм между $X$ и любым другим графом может быть проверен 4-мерным алгоритмом Вейсфейлера-Лемана.
