Albert Vucaj (Technical University Vienna), Clones over finite sets up to minor-equivalence

Tue, 28 Feb 2023, 1:25 pm MST

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}$. In this talk, I will present a general overview of 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 particular, I will focus on rather natural questions such as: is this poset a lattice? Is it countable? Does it have atoms or coatoms?
Joint work with Manuel Bodirsky and Dmitriy Zhuk.

[slides] [video]