| Замыкания групп подстановок и проблема изоморфизма | |
| Васильев А. В.1 | |
| 1.1Институт математики им. С.Л. Соболева СО РАН | |
| Дата поступления 2023.12.28 | Аннотация. Проблема изоморфизма графов состоит в нахождении наиболее эффективного алгоритма проверки изоморфизма двух данных конечных графов. Несмотря на значительные усилия многих математиков в последние 50 лет, время работы лучших из предложенных алгоритмов остается по существу экспоненциальным. Прорывом в этой области стал результат Л. Бабаи, предлагающий квазиполиномиальный алгоритм проверки изоморфизма графов. Основные составляющие этого алгоритма: теория конечных групп подстановок, многомерные когерентные конфигурации и алгоритмы Бабаи -- Лакса и Вейсфейлера -- Лемана. В работе идет речь о замыканиях групп подстановок и связи проблемы нахождения таких замыканий и проблемы изоморфизма графов.} % это аннотация статьи на русском языке. Постарайтесь сделать развернутую аннотацию. \keywords{группа подстановок, $m$-орбита, $m$-замыкание группы подстановок, конечный граф, многомерная когерентная конфигурация, проблема изоморфизма |
| Ключевые слова группа подстановок, $m$-орбита, $m$-замыкание группы подстановок, конечный граф, многомерная когерентная конфигурация, проблема изоморфизма | |
Библиография \bibitem{Vasilev1} Babai L. Groups, Graphs, Algorithms: The Graph Isomorphism Problem. Proc. ICM 2018, Rio de Janeiro. V.~3. P.~3303-3320 (see also Babai L. Graph Isomorphism in Quasipolynomial Time (2015), arXiv:1512.03547). \bibitem{Vasilev2} Wielandt H. Permutation groups through invariant relations and invariant functions. Lect. Notes Dept. Math. Ohio St. Univ., Columbus, 1969. \bibitem{Vasilev3} Higman D.G. Coherent configurations // I. Rend. Sem. Mat. Univ. Padova. 1970. V.~44. P.~1-25. \bibitem{Vasilev4} Вейсфейлер Б.Ю., Леман А.А. Приведение графа к каноническому виду и возникающая при этом алгебра // НТИ. Сер. 2. Информ. анализ. 1968. N.~9, С.~12-16. \bibitem{Vasilev5} Churikov D., Ponomarenko I. On 2-closed abelian permutation groups // Comm. Algebra 2022. V.~50. P.~1792-1801. \bibitem{Vasilev6} Ponomarenko I. Graph isomorphism problem and 2-closed permutation groups // Appl. Algebra Eng. Comm. Comput. 1994. V.~5. P.~9-22. \bibitem{Vasilev7} Evdokimov S. and Ponomarenko I. Two-closure of odd permutation group in polynomial time // Discrete Math. 2001. V.~235. P.~221-232. \bibitem{Vasilev8} Васильев А.В., Чуриков Д.В. $2$-Замыкание $\frac{3}{2}$-транзитивных групп за полиномиальное время~// Сиб. мат. журн. 2019. Т.~60, N.~2. C.~360-375. \bibitem{Vasilev9} Skresanov S.V. Two-closure of rank~3 groups in polynomial time // J. Algebra, 2023. V.~633. P.~906-934. \bibitem{Vasilev10} Seress A. The minimal base size of primitive solvable permutation groups // J. London Math. Soc. 1996. V.~53. P.~243-255. \bibitem{Vasilev11} O'Brien E.A., Ponomarenko I., Vasil'ev~A.V., Vdovin~E. The $3$-closure of a solvable permutation group is solvable // J.~Algebra, 2022, V.~607. P.~618-637. \bibitem{Vasilev12} Ponomarenko I., Vasil'ev~A.V. On computing the closures of solvable permutation groups, see arXiv:2304.02817. \bibitem{Vasilev13} Ponomarenko I., Vasil'ev~A.V. Two-closures of supersolvable permutation groups in polynomial time // Comput. Complexity. 2020. Vol.~29, Paper no.~5 (33 pages). | |
Сведения о финансировании и благодарности Работа выполнена в рамках государственного задания ИМ СО РАН, тема FWNF-2022-0002. | |
| {Closures of permutation groups and the isomorphism problem | |
| Vasil’ev A. V.1 | |
| 1.1Sobolev Institute of Mathematics SB RAS | |
| Received 2023.12.28 | Abstract. {Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russia} % Организация \abstractEng{The graph isomorphism problem consists of finding the most efficient algorithm for checking the isomorphism of two given finite graphs. Despite significant efforts by many mathematicians over the past 50 years, the running times of the best proposed algorithms remain essentially exponential. A breakthrough in this area was the result of L. Babai, who proposed a quasipolynomial algorithm for checking the isomorphism of graphs. The main components of this algorithm: theory of finite permutation groups, multidimensional coherent configurations and the Babai-Luks and Weisfeiler-Leman algorithms. The paper deals with the closures of permutation groups and the connection between the problem of finding such closures and the graph isomorphism problem. |
| Keywords permutation group, $m$-orbit, $m$-closure of a permutation group, finite graph, multidimensional coherent configuration, isomorphism problem | |
References \bibitem{Vasilev1} Babai L. Groups, Graphs, Algorithms: The Graph Isomorphism Problem. Proc. ICM 2018, Rio de Janeiro. V.~3. P.~3303-3320 (see also Babai L. Graph Isomorphism in Quasipolynomial Time (2015), arXiv:1512.03547). \bibitem{Vasilev2} Wielandt H. Permutation groups through invariant relations and invariant functions. Lect. Notes Dept. Math. Ohio St. Univ., Columbus, 1969. \bibitem{Vasilev3} Higman D.G. Coherent configurations // I. Rend. Sem. Mat. Univ. Padova. 1970. V.~44. P.~1-25. \bibitem{Vasilev4} Вейсфейлер Б.Ю., Леман А.А. Приведение графа к каноническому виду и возникающая при этом алгебра // НТИ. Сер. 2. Информ. анализ. 1968. N.~9, С.~12-16. \bibitem{Vasilev5} Churikov D., Ponomarenko I. On 2-closed abelian permutation groups // Comm. Algebra 2022. V.~50. P.~1792-1801. \bibitem{Vasilev6} Ponomarenko I. Graph isomorphism problem and 2-closed permutation groups // Appl. Algebra Eng. Comm. Comput. 1994. V.~5. P.~9-22. \bibitem{Vasilev7} Evdokimov S. and Ponomarenko I. Two-closure of odd permutation group in polynomial time // Discrete Math. 2001. V.~235. P.~221-232. \bibitem{Vasilev8} Васильев А.В., Чуриков Д.В. $2$-Замыкание $\frac{3}{2}$-транзитивных групп за полиномиальное время~// Сиб. мат. журн. 2019. Т.~60, N.~2. C.~360-375. \bibitem{Vasilev9} Skresanov S.V. Two-closure of rank~3 groups in polynomial time // J. Algebra, 2023. V.~633. P.~906-934. \bibitem{Vasilev10} Seress A. The minimal base size of primitive solvable permutation groups // J. London Math. Soc. 1996. V.~53. P.~243-255. \bibitem{Vasilev11} O'Brien E.A., Ponomarenko I., Vasil'ev~A.V., Vdovin~E. The $3$-closure of a solvable permutation group is solvable // J.~Algebra, 2022, V.~607. P.~618-637. \bibitem{Vasilev12} Ponomarenko I., Vasil'ev~A.V. On computing the closures of solvable permutation groups, see arXiv:2304.02817. \bibitem{Vasilev13} Ponomarenko I., Vasil'ev~A.V. Two-closures of supersolvable permutation groups in polynomial time // Comput. Complexity. 2020. Vol.~29, Paper no.~5 (33 pages). | |
Acknowledgements Работа выполнена в рамках государственного задания ИМ СО РАН, тема FWNF-2022-0002. | |
| Сведения об авторах Васильев А. В. 1.1 |
| About the authors Vasil’ev A. V. 1.1 |
