Structures preserved by primitive actions of S_ω

2025/01/07 by Manuel Bodirsky, Bertalan Bodor, Bodirsky, Manuel +1 · 3 citations
Computer Science · Mathematics · #Advanced Algebra and Logic #Advanced Topology and Set Theory #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Rings, Modules, and Algebras

paper · pdf · doi:10.48550/arxiv.2501.03789

openalex publication_date 2025/01/07 · openalex created_date 2025/01/09 · openalex updated_date 2026/07/28

Abstract

We present a dichotomy for structures A that are preserved by primitive actions of S_ω = Sym(\mathbb N): such a structure primitively positively constructs all finite structures and the constraint satisfaction problem is NP-complete, or the constraint satisfaction problem for A is in P. To prove our result, we study the first-order reducts of the Johnson graph J(k), for k ≥ 2, whose automorphism group G equals the action of Sym(\mathbb N) on the set V of k-element subsets of \mathbb N. We use the fact that J(k) has a finitely bounded homogeneous Ramsey expansion and that G is a maximal closed subgroup of Sym(V).

Cited by

• Taking model-complete cores
• A CSP approach to Graph Sandwich Problems
• Structures with not too fast unlabelled growth

Related

• Reducts of Ramsey structures
• Equations in oligomorphic clones and the Constraint Satisfaction Problem for ω-categorical structures
• Constraint satisfaction problems for reducts of homogeneous graphs
• Structures with Small Orbit Growth
• Combinatorial Properties of Metrically Homogeneous Graphs