License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.27
URN: urn:nbn:de:0030-drops-169653
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16965/
Go to the corresponding LIPIcs Volume Portal

Brachter, Jendrik ; Schweitzer, Pascal

A Systematic Study of Isomorphism Invariants of Finite Groups via the Weisfeiler-Leman Dimension

pdf-format:
LIPIcs-ESA-2022-27.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{brachter_et_al:LIPIcs.ESA.2022.27,
  author =	{Brachter, Jendrik and Schweitzer, Pascal},
  title =	{{A Systematic Study of Isomorphism Invariants of Finite Groups via the Weisfeiler-Leman Dimension}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16965},
  URN =		{urn:nbn:de:0030-drops-169653},
  doi =		{10.4230/LIPIcs.ESA.2022.27},
  annote =	{Keywords: group isomorphism problem, Weisfeiler-Leman algorithms, group invariants, direct product decompositions}
}

Keywords: group isomorphism problem, Weisfeiler-Leman algorithms, group invariants, direct product decompositions
Collection: 30th Annual European Symposium on Algorithms (ESA 2022)
Issue Date: 2022
Date of publication: 01.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI