Laboratory of Mathematical Logic at PDMI

Вторник, 8 октября, Zoom. Начало в 15:00.

Докладчик: И.Н. Пономаренко (ПОМИ).

Тема: Вокруг проблемы изоморфизма.

Abstract

В докладе будут затронуты две проблемы теории сложности вычислений: распознавание изоморфизма (конечных) графов и групп, и нахождение группы автоморфизмов ``симметричных’' объектов. В первом части мы приведем несколько эквивалентных определений размерности Вейсфейлера-Лемана групп и графов, проследим связь этого инварианта с проблемой изоморфизма, и опишем два новых результата: об алгебраической природе этого инварианта [1] и о размерности Вейсфейлера-Лемана графов перествновок [2]. Во второй части, мы поговорим о многомерных комбинаторных объектах, возникающих из групп перестановок и опишем новый результат о вычислении полной группы автоморфизмов такого объекта в случае, когда исходная группа перестановок разрешима [3].

[1] G.Chen, Q.Ren, and I.Ponomarenko, On multidimensional Schur rings of finite groups, J. Group Theory, 27:1, 61-88 (2024), https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdoi.or....

[2] J. Guo, A.L.Gavrilyuk, and I.Ponomarenko, On the Weisfeiler-Leman dimension of permutation graphs, SIAM Journal on Discrete Mathematics, 38:2, 1193-1929 (2024), https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdoi.or....

[3] I.Ponomarenko and A.V.Vasil'ev, On computing the closures of solvable permutation groups, International J. Algebra and Computation, 34:1, 137-145 (2024), doi: 10.1142/S0218196724500036.