The Weisfeiler—Leman (WL) algorithm is a key combinatorial subroutine in Graph Isomorphism, that (for fixed ) computes an isomorphism invariant coloring of the k-tuples of vertices. Brachter & Schweitzer (LICS 2020) recently adapted WL to the setting of groups. Using a classical Ehrenfeucht-Fra\"iss\'e pebble game, we will show that Weisfeiler—Leman serves as a polynomial-time isomorphism test for several families of groups previously shown to be in by multiple methods. These families of groups include:
(1) Coprime extensions by , where is -generated and the normal Hall subgroup is Abelian (Qiao, Sarma, & Tang, STACS 2011).
(2) Groups without Abelian normal subgroups (Babai, Codenotti, & Qiao, ICALP 2012).
In both of these cases, the previous strategy involved identifying key group-theoretic structure that could then be leveraged algorithmically, resulting in different algorithms for each family. A common theme among these is that the group-theoretic structure is mostly about the action of one group on another. Our main contribution is to show that a single, combinatorial algorithm (Weisfeiler-Leman) can identify those same group-theoretic structures in polynomial time.
We also show that Weisfeiler—Leman requires only a constant number of rounds to identify groups from each of these families. Combining this result with the parallel WL implementation due to Grohe & Verbitsky (ICALP 2006), this improves the upper bound for isomorphism testing in each of these families from to .
This is joint work with Joshua A. Grochow.
Weisfeiler—Leman for Group Isomorphism: Action Compatibility
Apr. 19, 2022 2:30pm (MATH 3…
Lie Theory
Richard Green (CU Boulder)
X
A "2-root'' is a symmetrized tensor product of orthogonal roots of a Kac--Moody algebra. We study the 2-roots of the Weyl group W of a simply laced Y-shaped Dynkin diagram with three branches of arbitrary finite lengths. The symmetric square of the reflection representation of W has a natural codimension-1 submodule with a canonical basis of 2-roots. We will discuss some of the remarkable properties of this basis. (This is joint work with Tianyuan Xu.)
Groups can be described as quotients of free groups by relations. This basic fact has a categorical generalization called the Beck monadicity theorem. As I will explain, that is a statement about monads associated to "nice" adjoint pairs of functors, in this case the free functor from sets to groups and the forgetful functor from groups to sets. It is a lovely result when it holds, but adjoint functors are ubiquitous and they are usually not "nice".
In homotopy theory, it is very important to understand "homotopical monadicity theorems" which say when something like the conclusion of the monadicity theorem holds "up to homotopy''. I have worked on this question for over half a century, but I have only reached conceptual understanding of what I have been doing all along in the last few months, in joint work with Hana Kong and Foling Zou. The understanding leads to new applications. I will try to explain the basic ideas in as elementary a way as I can.
Homotopical Monadicity Theorem Sponsored by the Meyer Fund
Weisfeiler—Leman for Group Isomorphism: Action Compatibility