Finite simple groups in the primitive positive constructability poset

Read full text
Authors: Sebastian Meyer, Florian Starke
Cited by: 0

Abstract

Primitive positive constructions between relational structures are motivated by computational complexity of constraint satisfaction problems. They induce a partial order on equivalence classes of finite relational structures. We show that this order has an infinite third layer, given by the equivalence class of an oriented graph and of infinitely many permutation groups that are abstractly isomorphic to all the finite simple groups in a one-to-one correspondence. More concretely, the two topmost layers of the primitive positive constructability poset are known to consist of a single element each. We consider [Formula: see text], a representative of the element in the second layer, and its polymorphism clone [Formula: see text]. We show that any clone over a finite domain that admits a quasi-Maltsev operation and fully symmetric operations of all arities admits an incoming minion homomorphism from [Formula: see text]. We use this result to show that in the primitive positive contructability poset, the lower covers of [Formula: see text] are represented by the transitive tournament on three vertices and for each finite simple group by the disjoint union of all its primitive group actions.

Fields of Study & Subjects

Rings Modules and Algebras Computability Logic AI Algorithms

Publication details

Journal / source
International Journal of Algebra and Computation
Publisher
World Scientific Pub Co Pte Ltd
Pages
1–28
Publication date
18 July 2026
Language
EN