The simultaneous conjugacy problem in the symmetric group
HTML articles powered by AMS MathViewer
- by Andrej Brodnik, Aleksander Malnič and Rok Požar HTML | PDF
- Math. Comp. 90 (2021), 2977-2995 Request permission
Abstract:
The transitive simultaneous conjugacy problem asks whether there exists a permutation $\tau \in S_n$ such that $b_j = \tau ^{-1} a_j \tau$ 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(dn^2)$ time. An algorithm with running time $O(dn \log (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 \log d / \log n + dn\log n)$ 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$.References
- A. Brodnik, A. Malnič, R. Požar, A subquadratic algorithm for the simultaneous conjugacy problem, 2020, arXiv:12007.05870 [math.CO].
- Andrej Brodnik and J. Ian Munro, Membership in constant time and almost-minimum space, SIAM J. Comput. 28 (1999), no. 5, 1627–1640. MR 1694180, DOI 10.1137/S0097539795294165
- Reinhard Diestel, Graph theory, 3rd ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 2005. MR 2159259
- Bettina Eick, Tommy Hofmann, and E. A. O’Brien, The conjugacy problem in $\textrm {GL}(n, \Bbb Z)$, J. Lond. Math. Soc. (2) 100 (2019), no. 3, 731–756. MR 4048718, DOI 10.1112/jlms.12246
- Max Fontet, Calcul de centralisateur d’un groupe de permutations, Bull. Soc. Math. France Mém. 49-50 (1977), 53–63 (French). MR 476836, DOI 10.24033/msmf.214
- The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.11.0, http://www.gap-system.org, 2020.
- Juan González-Meneses, Improving an algorithm to solve multiple simultaneous conjugacy problems in braid groups, Geometric methods in group theory, Contemp. Math., vol. 372, Amer. Math. Soc., Providence, RI, 2005, pp. 35–42. MR 2139675, DOI 10.1090/conm/372/06872
- Christoph M. Hoffmann, Subcomplete generalizations of graph isomorphism, J. Comput. System Sci. 25 (1982), no. 3, 332–359. MR 684264, DOI 10.1016/0022-0000(82)90015-0
- Derek F. Holt, Bettina Eick, and Eamonn A. O’Brien, Handbook of computational group theory, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2005. MR 2129747, DOI 10.1201/9781420035216
- J. E. Hopcroft and R. E. Tarjan, A $V$ $\textrm {log}\ V$ algorithm for isomorphism of triconnected planar graphs, J. Comput. System Sci. 7 (1973), 323–331. MR 345442, DOI 10.1016/S0022-0000(73)80013-3
- Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt, Fast pattern matching in strings, SIAM J. Comput. 6 (1977), no. 2, 323–350. MR 451916, DOI 10.1137/0206024
- Aleksander Malnič, Roman Nedela, and Martin Škoviera, Lifting graph automorphisms by voltage assignments, European J. Combin. 21 (2000), no. 7, 927–947. MR 1787907, DOI 10.1006/eujc.2000.0390
- Aleksander Malnič, Roman Nedela, and Martin Škoviera, Regular homomorphisms and regular maps, European J. Combin. 23 (2002), no. 4, 449–461. MR 1914482, DOI 10.1006/eujc.2002.0568
- Ákos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. MR 1970241, DOI 10.1017/CBO9780511546549
- M. A. Sridhar, A fast algorithm for testing isomorphism of permutation networks, IEEE Trans. Comput. 38 (1989), no. 6, 903–909. MR 999482, DOI 10.1109/12.24304
- A. Yavuz Oruç, M. Yaman Oruç, On testing isomorphism of permutation networks, IEEE Trans. Computers (TC) 34 (1985), 958-962.
Additional Information
- Andrej Brodnik
- Affiliation: University of Primorska, UP FAMNIT, Glagoljaška 8, 6000 Koper, Slovenia; and University of Primorska, UP IAM, Muzejski trg 2, 6000 Koper, Slovenia; and University of Ljubljana, UL FRI, Večna pot 113, 1000 Ljubljana, Slovenia
- MR Author ID: 623283
- ORCID: 0000-0001-9773-0664
- Aleksander Malnič
- Affiliation: University of Primorska, UP IAM, Muzejski trg 2, 6000 Koper, Slovenia; and University of Ljubljana, UL PEF, Kardeljeva pl. 16, 1000 Ljubljana, Slovenia; and IMFM, Jadranska 19, 1000 Ljubljana, Slovenia
- Rok Požar
- Affiliation: University of Primorska, UP FAMNIT, Glagoljaška 8, 6000 Koper, Slovenia; and University of Primorska, UP IAM, Muzejski trg 2, 6000 Koper, Slovenia; and IMFM, Jadranska 19, 1000 Ljubljana, Slovenia
- Received by editor(s): January 28, 2020
- Received by editor(s) in revised form: November 28, 2020, and December 29, 2020
- Published electronically: June 24, 2021
- Additional Notes: The first author was sponsored in part by the Slovenian Research Agency (research program P2-0359 and research projects J1-2481, J2-2504, and N2-0171). The second author was sponsored in part by the Slovenian Research Agency (research program P1-0285 and research projects N1-0062, J1-9108, J1-9110, J1-9187, J1-1694, J1-1695). The third author was sponsored in part by the Slovenian Research Agency (research program P1-0404 and research projects N1-0062, J1-9110, J1-9187, J1-1694).
The third author is the corresponding author. - © Copyright 2021 American Mathematical Society
- Journal: Math. Comp. 90 (2021), 2977-2995
- MSC (2000): Primary 05C85, 05C60
- DOI: https://doi.org/10.1090/mcom/3637
- MathSciNet review: 4305377