2026-08-16T20:12:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16965 2024-03-06T10:58:50Z ddc:004 open_access

A Systematic Study of Isomorphism Invariants of Finite Groups via the Weisfeiler-Leman Dimension Brachter, Jendrik Schweitzer, Pascal group isomorphism problem Weisfeiler-Leman algorithms group invariants direct product decompositions We investigate the relationship between various isomorphism invariants for finite groups. Specifically, we use the Weisfeiler-Leman dimension (WL) to characterize, compare and quantify the effectiveness and complexity of invariants for group isomorphism. It turns out that a surprising number of invariants and characteristic subgroups that are classic to group theory can be detected and identified by a low dimensional Weisfeiler-Leman algorithm. These include the center, the inner automorphism group, the commutator subgroup and the derived series, the abelian radical, the solvable radical, the Fitting group and π-radicals. A low dimensional WL-algorithm additionally determines the isomorphism type of the socle as well as the factors in the derives series and the upper and lower central series. We also analyze the behavior of the WL-algorithm for group extensions and prove that a low dimensional WL-algorithm determines the isomorphism types of the composition factors of a group. Finally we develop a new tool to define a canonical maximal central decomposition for groups. This allows us to show that the Weisfeiler-Leman dimension of a group is at most one larger than the dimensions of its direct indecomposable factors. In other words the Weisfeiler-Leman dimension increases by at most 1 when taking direct products. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jendrik Brachter and Pascal Schweitzer 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.27 urn:nbn:de:0030-drops-169653 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.27 eng https://creativecommons.org/licenses/by/4.0/legalcode