The simultaneous conjugacy problem in the symmetric group

DOI10.1090/MCOM/3637MaRDI QIDQ4956934zbMATH OpenOpenAlexFDO

Authors Andrej Brodnik, Aleksander Malnič, Rok Požar

Publication date 2 September 2021

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.07889

zbMATH Keywords

graph isomorphismdivide-and-conquertruncated iterationsimultaneous conjugacy problemfast multiplication algorithmpermutation multiplication

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Symmetric groups (20B30)

Abstract: The transitive simultaneous conjugacy problem asks whether there exists a permutation $auin{S}_n$ such that $b_j=a{u}^{-1}{a}_{j}au$ holds for all $j=1,2,ldots,d$, where $a_1,a_2,ldots,a_d$ and $b_1,b_2,ldots,b_d$ are given sequences of $d$ permutations in $S_n$, each of which generates a transitive subgroup of $S_n$. As from mid 70' it has been known that the problem can be solved in $O(d{n}^2)$ time. An algorithm with running time $O(dnlog(dn))$, proposed in late 80', does not work correctly on all input data. In this paper we solve the transitive simultaneous conjugacy problem in $O(n^{2}logd/logn+dnlogn)$ time and $O(n^{3/2}+dn)$ space. Experimental evaluation on random instances shows that the expected running time of our algorithm is considerably better, perhaps even nearly linear in $n$ at given $d$.

Recommendations

• A subquadratic algorithm for the simultaneous conjugacy problem
• Fast Management of Permutation Groups I
• scientific article; zbMATH DE number 3968860
• Permutation group algorithms based on partitions. I: Theory and algorithms
• On simultaneous conjugation of permutations

Cites work

• scientific article; zbMATH DE number 3585658 (Why is no real title available?)
• scientific article; zbMATH DE number 2133330 (Why is no real title available?)
• scientific article; zbMATH DE number 1849958 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 2209669 (Why is no real title available?)
• A V log V algorithm for isomorphism of triconnected planar graphs
• A fast algorithm for testing isomorphism of permutation networks
• Fast Pattern Matching in Strings
• Lifting graph automorphisms by voltage assignments
• Membership in Constant Time and Almost-Minimum Space
• Reconfiguration Algorithms for Interconnection Networks
• Regular homomorphisms and regular maps
• Subcomplete generalizations of graph isomorphism
• The conjugacy problem in \(\mathrm{ Gl } ( n, \mathbb{Z} )\)

Cited in

(6)

• scientific article; zbMATH DE number 3966382 (Why is no real title available?)
• A linear-time algorithm for the orbit problem over cyclic groups
• A subquadratic algorithm for the simultaneous conjugacy problem
• scientific article; zbMATH DE number 3975219 (Why is no real title available?)
• A Symmetry Criterion for Conjugacy in Finite Groups
• On simultaneous conjugation of permutations

Describes a project that uses

Uses Software

• GAP

This page was built for publication: The simultaneous conjugacy problem in the symmetric group

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4956934)