The simultaneous conjugacy problem in the symmetric group

DOI10.1090/MCOM/3637zbMATH Open1471.05100arXiv1907.07889OpenAlexW3127554214MaRDI QIDQ4956934FDOQ4956934

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

Publication date: 2 September 2021

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

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

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lifting graph automorphisms by voltage assignments
• Fast Pattern Matching in Strings
• Regular homomorphisms and regular maps
• Membership in Constant Time and Almost-Minimum Space
• Title not available (Why is that?)
• A V log V algorithm for isomorphism of triconnected planar graphs
• The conjugacy problem in \(\mathrm{ Gl } ( n, \mathbb{Z} )\)
• Subcomplete generalizations of graph isomorphism
• Title not available (Why is that?)
• A fast algorithm for testing isomorphism of permutation networks
• Reconfiguration Algorithms for Interconnection Networks

Cited In (6)

• A linear-time algorithm for the orbit problem over cyclic groups
• A subquadratic algorithm for the simultaneous conjugacy problem
• Title not available (Why is that?)
• A Symmetry Criterion for Conjugacy in Finite Groups
• On simultaneous conjugation of permutations
• Title not available (Why is that?)

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)