Two-closure of rank 3 groups in polynomial time

DOI10.1016/J.JALGEBRA.2023.04.034MaRDI QIDQ6170785zbMATH OpenOpenAlexFDO

Authors Saveliĭ Vyacheslavovich Skresanov

Publication date 10 August 2023

Published in Journal of Algebra (Search for Journal in Brave)

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

zbMATH Keywords

\(2\)-closurepermutation grouppolynomial timerank \(3\)

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Software, source code, etc. for problems pertaining to group theory (20-04) General theory for finite permutation groups (20B05) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Generators, relations, and presentations of groups (20F05) Analysis of algorithms and problem complexity (68Q25)

Abstract: A finite permutation group $G$ on $Omega$ is called a rank 3 group if it has precisely three orbits in its induced action on $OmegaimesOmega$. The largest permutation group on $Omega$ having the same orbits as $G$ on $OmegaimesOmega$ is called the 2-closure of $G$. We construct a polynomial-time algorithm which given generators of a rank 3 group computes generators of its 2-closure.

Review text

Let \(G\) be a permutation group on a finite set \(\Omega\). The orbits of \(G\) on \(\Omega \times \Omega\) are called \(2\)-orbits. The set of \(2\)-orbits of \(G\) forms a coherent configuration. The number of \(2\)-orbits is called the rank of \(G\). The largest permutation group (acting on \(\Omega\)) having the same \(2\)-orbits as \(G\) is called the \(2\)-closure of \(G\) and is denoted by \(G^{(2)}\). Given generators of a rank \(3\) group \(G\), the paper under review provides a polynomial-time algorithm (in \(|\Omega|\)) to compute generators for \(G^{(2)}\). In many cases, not only \(G^{(2)}\) is constructed but the corresponding rank \(3\) graph is also recognized. The work is related to the graph isomorphism problem, in particular to the problem of computing generators of the full automorphism group of a given graph (see [\textit{R. Mathon}, Inf. Process. Lett. 8, 131--132 (1979; Zbl 0395.68057)]). In this context \(G^{(2)}\) was computed for \(G\) a group of odd order [\textit{S. Evdokimov} and \textit{I. Ponomarenko}, Discrete Math. 235, No. 1--3, 221--232 (2001; Zbl 0982.20005)], for a nilpotent group [\textit{I. N. Ponomarenko}, Appl. Algebra Eng. Commun. Comput. 5, No. 1, 9--22 (1994; Zbl 0803.20003)], for a \(3/2\)-transitive group [\textit{A. V. Vasil'ev} and \textit{D. V. Churikov}, Sib. Math. J. 60, No. 2, 279--290 (2019; Zbl 1512.20006); translation from Sib. Mat. Zh. 60, No. 2, 360--375 (2019)], and for a supersolvable group [\textit{I. Ponomarenko} and \textit{A. Vasil'ev}, Comput. Complexity 29, No. 1, Paper No. 5, 33 p. (2020; Zbl 1484.20002)].

Recommendations

• The 2-closure of a \(\frac{3}{2}\)-transitive group in polynomial time
• Two-closure of odd permutation group in polynomial time
• On primitive 2-closed permutation groups of rank at most four
• Graph isomorphism problem and 2-closed permutation groups
• 2-closures of primitive permutation groups of holomorph type

Cites work

• A note on the graph isomorphism counting problem
• Base size, metric dimension and other invariants of groups and graphs
• Computing the order of centralizers in linear groups
• Computing the structure of finite algebras
• Finite Permutation Groups and Finite Simple Groups
• Generation of almost simple groups
• Generators for Simple Groups
• Graph isomorphism problem and 2-closed permutation groups
• scientific article; zbMATH DE number 3884354 (Why is no real title available?)
• scientific article; zbMATH DE number 3906699 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 46357 (Why is no real title available?)
• scientific article; zbMATH DE number 1253966 (Why is no real title available?)
• scientific article; zbMATH DE number 2007658 (Why is no real title available?)
• scientific article; zbMATH DE number 1849958 (Why is no real title available?)
• scientific article; zbMATH DE number 3412859 (Why is no real title available?)
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Isomorphism of planar graphs (working paper)
• Matrix generators for the orthogonal groups
• On 2-closures of rank 3 groups
• On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
• Partial linear spaces with a rank 3 affine primitive group of automorphisms
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Polynomial-time normalizers
• Recognizing Hamming graphs in linear time and space
• Strongly regular graphs
• Sylow's theorem in polynomial time
• The 2-closure of a \(\frac{3}{2}\)-transitive group in polynomial time
• The Affine Permutation Groups of Rank Three
• The Finite Primitive Permutation Groups of Rank Three
• The Finite Simple Groups
• The isomorphism problem for classes of graphs closed under contraction
• The Rank 3 Permutation Representations of the Finite Classical Groups
• Two-closure of odd permutation group in polynomial time
• Two-closures of supersolvable permutation groups in polynomial time

Cited in

(7)

• Graph isomorphism problem and 2-closed permutation groups
• The 2-closure of a \(\frac{3}{2}\)-transitive group in polynomial time
• On 2-closures of rank 3 groups
• Two-closure of odd permutation group in polynomial time
• On computing the closures of solvable permutation groups
• Reduction of the group isomorphism problem to the group automorphism problem
• Two-closures of supersolvable permutation groups in polynomial time

This page was built for publication: Two-closure of rank \(3\) groups in polynomial time

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