论文标题
在有限群体的Weisfeiler-Lean维度上
On the Weisfeiler-Leman Dimension of Finite Groups
论文作者
论文摘要
与图形相比，有限组的同构问题的组合方法比代数较低。为了能够研究有限组的描述性复杂性和同构问题，我们为组定义了weisfeiler-leman算法。实际上，我们定义了算法的三个版本。与图形相比，三个类似版本很容易同意的图形相反，对于群体而言，情况更加复杂。对于小组，我们表明它们的表现力是线性相关的。我们还对每个版本的逻辑和杂志卵石游戏进行了描述。 为了构建群体的示例，我们设计了一个同构和非同态性，从而保留了从图到组的转变。使用高weisfeiler-leman维度的图，我们构建高度相似但非同构的群体，具有等量$θ（\ sqrt {\ sqrt {\ log n}）$ - 子组 - 群 - 群 - 群体 - weisfeiler-leman dimension 3。具有高度相似的通勤图。 结果表明，与基于相似的组合构建体区分图相比，Weisfeiler-Leman算法可以在区分组方面更有效。
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 $Θ(\sqrt{\log n})$-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.
