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