Jendrik Brachter

"On the Weisfeller-Leman Dimension for Finite Groups"

The group isomorphism problem (GrI) is one of the most fundamental problems in group theory for which we do not have efficient algorithmic tools. In fact, its complexity is not well understood at all and, despite decades of active research, even for very limited classes of groups the best known bounds are only slightly better than the basic n^O(log(n)) bound obtained from guessing generating sets. As GrI is polynomial-time reducible to graph isomorphism it furthermore constitutes another natural candidate for an NP-intermediate problem.In comparison to graphs, combinatorial tools for the group isomorphism problem are much less developed. For graphs, an important tool in this scope are the Weisfeiler-Leman algorithms. These provide simple but universal and effective combinatorial methods for distinguishing non-isomorphic graphs. They are strongly linked to the descriptive complexity of graphs and while their limits have been firmly established, they can be very successful in many situations. In this talk, parts of our work on defining and investigating Weisfeiler-Leman algorithms for groups will be presented. I will first give a brief overview on the group isomorphism problem and its connections to graph isomorphism. Afterwards, I will introduce Weisfeiler-Leman algorithms for groups and compare them with their classical analogues. Finally, I will discuss first results on the Weisfeiler-Leman dimension of finite groups. More explicitely, I will construct an infinite family of pairs of groups which agree in many traditional isomorphism invariants but can be distinguished from all other groups by 3-dimensional WL-refinement.

Termin als Datei downloaden und in den Kalender importieren.