Вторник 08.10. И.Н. Пономаренко (ПОМИ): "Вокруг проблемы изоморфизма"

[PDMI seminars]

Семинар по дискретной математике

Тема: Вокруг проблемы изоморфизма
Место: Zoom
Время: 08.10.2024, 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.org%2F10.1515%2Fjgth-2023-0032&data=05%7C02%7Cmasnnv%40bath.ac.uk%7Cab75aeafe2eb41093fcf08dce11c3f65%7C377e3d224ea1422db0ad8fcc89406b9e%7C0%7C0%7C638632758655309029%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=UJAwhyMkRUcxCfg%2BKLRZ5U7ESx4I87Uo93LSUXsG9D8%3D&reserved=0.

[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.org%2F10.1137%2F23M1575019&data=05%7C02%7Cmasnnv%40bath.ac.uk%7Cab75aeafe2eb41093fcf08dce11c3f65%7C377e3d224ea1422db0ad8fcc89406b9e%7C0%7C0%7C638632758655324626%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=ynLAN71fRom%2F6GGOYgyH0rODr310vJzBJW6GmjoABxs%3D&reserved=0.

[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.