Structures preserved by primitive actions of S omega

arXiv:2501.03789 · math.LO, cs.CC · Submitted 2025-01-07 · Read on arXiv

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

Related papers