On the Weisfeiler-Leman dimension of finite groups

DOI10.1145/3373718.3394786MaRDI QIDQ5145641zbMATH OpenOpenAlexFDO

Authors Jendrik Brachter, P. Schweitzer

Publication date 21 January 2021

Published in Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Cai-Frer-Immermann graphsgroup isomorphismlogics with countingWeisfeiler-Leman dimension

Mathematics Subject Classification ID

Other nonclassical logic (03B60) Model theory of finite structures (03C13) Computational methods for problems pertaining to group theory (20-08) Arithmetic and combinatorial problems involving abstract finite groups (20D60)

Abstract: In comparison to graphs, combinatorial methods for the isomorphism problem of finite groups are less developed than algebraic ones. To be able to investigate the descriptive complexity of finite groups and the group isomorphism problem, we define the Weisfeiler-Leman algorithm for groups. In fact we define three versions of the algorithm. In contrast to graphs, where the three analogous versions readily agree, for groups the situation is more intricate. For groups, we show that their expressive power is linearly related. We also give descriptions in terms of counting logics and bijective pebble games for each of the versions. In order to construct examples of groups, we devise an isomorphism and non-isomorphism preserving transformation from graphs to groups. Using graphs of high Weisfeiler-Leman dimension, we construct highly similar but non-isomorphic groups with equal $Theta(sqrtlogn)$-subgroup-profiles, which nevertheless have Weisfeiler-Leman dimension 3. These groups are nilpotent groups of class 2 and exponent $p$, they agree in many combinatorial properties such as the combinatorics of their conjugacy classes and have highly similar commuting graphs. The results indicate that the Weisfeiler-Leman algorithm can be more effective in distinguishing groups than in distinguishing graphs based on similar combinatorial constructions.

Recommendations

• The Weisfeiler-Leman algorithm and recognition of graph properties
• On Weisfeiler-Leman invariance: subgraph counts and related graph properties
• The Weisfeiler-Leman algorithm and recognition of graph properties
• Isomorphism testing for embeddable graphs through definability
• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3

Cited in

(13)

• The Weisfeiler-Leman algorithm and the diameter of Schreier graphs
• Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting)
• Connections between graphs and matrix spaces
• On multidimensional Schur rings of finite groups
• Faster isomorphism for p-groups of class 2 and exponent p
• Count-free Weisfeiler-Leman and group isomorphism
• Tuple regularity and \(\mathrm{k} \)-ultrahomogeneity for finite groups
• Complexity of identifying fitting-free groups
• On the descriptive complexity of groups without abelian normal subgroups
• On the parallel complexity of group isomorphism via Weisfeiler-Leman
• On the descriptive complexity of groups without abelian normal subgroups (extended abstract)
• A systematic study of isomorphism invariants of finite groups via the Weisfeiler-Leman dimension
• Parallel complexity of identifying groups and quasigroups via decompositions

This page was built for publication: On the Weisfeiler-Leman dimension of finite groups

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