Algebra Seminar talk
2023-03-24
Albert Vucaj
Clones over finite sets up to minor-equivalence
Abstract:
Achieving a classification of all clones of operations over a finite set is one of the goals at the heart of universal algebra. Over the years, it has been shown that such a goal seems arduously reachable even if we only focus on clones over three-element sets. In a recent turn of events, the minor-equivalence relation on clones over finite sets gained importance both in universal algebra and in computer science: minor-equivalent clones satisfy the same set identities of the form $f(x_1,\dots,x_n)\approx g(y_1,\dots,y_m)$, also known as minor-identities. Moreover, it was proved that the complexity of the CSP of a finite structure $\mathbb{A}$ only depends on the set of minor-identities satisfied by the polymorphism clone of $\mathbb{A}$. We focus on the poset arising by considering clones over some finite set with the following order: we write $\mathcal{C} \leq \mathcal{D}$ if there exist a minor-preserving map from $\mathcal{C}$ to $\mathcal{D}$. In this talk, I will provide an overview of basic results concerning the aforementioned poset and discuss some open problems.