Structures preserved by primitive actions of S omega
math.LO, cs.CC
Submitted: 2025-01-07
Updated: 2026-11-18
Comments: 34 pages plus references; accepted for publication in LMCS
License: http://creativecommons.org/licenses/by-sa/4.0/
The gist: We present a dichotomy for structures A that are preserved by primitive actions of S ω = Sym(N): such a structure primitively positively constructs all finite structures and the constraint…
Terminology
Abstract
We present a dichotomy for structures A that are preserved by primitive actions of S ω = Sym(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 at least 2, whose automorphism group G equals the action of Sym(N) on the set V of k-element subsets of 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).
Sources
- Structures with Small Orbit Growth
- Taking model-complete cores
- Datalog-Expressibility for Monadic and Guarded Second-Order Logic
- Monadic stability and growth rates of $\omega$-categorical structures
- Smooth approximations and CSPs over finitely bounded homogeneous structures
- Minimal operations over permutation groups
- A Proof of the CSP Dichotomy Conjecture
Related papers
- The consistency strength of the failure of amenable C-sequences
- Classification of bipartite observables III: simplicity, mixtures and quantum error correction
- Indiscernible Extraction in Theories with Bounded k-splitting
- Measuring the Complexity of Countable Presburger Models
- A non-trivially non-trivial automorphism at an inaccessible cardinal
- The Ordering Principle and Higher Dependent Choice