G-terms and the local-global property

Abstract: Let $G$ be a permutation group on a $n$-element set. We then say that an algebra $\mathbf A$ has a $G$-term $t(x_1,\ldots,x_n)$, if $t$ is invariant under permuting its variables according to $G$, i.e. $\mathbf A \models t(x_1,\ldots,x_n) \approx t(x_{\pi(1)},\ldots,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 $Sym(n)$ for $n \geq 3$.

This is joint work with Alexandr Kazda.

computational complexitycategory theorylogic

Audience: researchers in the topic

PALS Panglobal Algebra and Logic Seminar

Series comments: The PALS seminar is a research and learning seminar organized by the algebra and logic research group of the Department of Mathematics at the University of Colorado at Boulder. The scope of the seminar includes all topics with links to algebra, logic, or their applications, like general algebra, logic, model theory, category theory, set theory, set-theoretic topology, or theoretical computer science. Please contact one of the organizers for the Zoom password, to join the mailing list or if you want to speak.