Tue, 30 Nov 2021, 12 pm MST
Let G be a permutation group on an n-element set. We then say that an algebra A has a G-term t(x_1,...,x_n), if t is invariant under permuting its variables according to G, i.e. A models t(x_1,...,x_n) = t(x_{\pi(1)},...,x_{\pi(n)}) for all \pi in G. Since G-terms appear in the study of constraint satisfaction problems and elsewhere, it is natural to ask for their classification up to interpretability. In the first part of my talk I would like to share a few partial results on this problem.
In the second part I am going to discuss the complexity of deciding whether a given finite algebra has a G-term. The most commonly used strategy in showing that deciding a given Maltsev condition is in P, is to show that it suffices to check the condition locally (i.e. on subsets of bounded size). We show that this „local-global“ approach works for all G-terms induced by regular permutation groups G (and direct products of them), but fails for some other „rich enough" permutation groups, such as S_n for n > 2.
This is joint work with Alexandr Kazda.