Structures preserved by primitive actions of $S_ω$
We present a dichotomy for structures $A$ that are preserved by primitive actions of $S_ω = \text{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 \geq 2$, whose automorphism group $G$ equals the action of $\text{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 $\text{Sym}(V)$.
Authors
- Bertalan Bodor (ORCID: https://orcid.org/0009-0003-6679-6355)
- Manuel Bodirsky (ORCID: https://orcid.org/0000-0001-8228-3611)
Publication Details
- Journal
- Logical Methods in Computer Science
- Published
- 2026-11-19
- DOI
- https://doi.org/10.46298/lmcs-22(4:21)2026
- Citations
- 6
- Primary Topic
- Advanced Topology and Set Theory
- Type
- article
- Field-Weighted Citation Impact
- 5.63
Funders
- European Commission
- Deutsche Forschungsgemeinschaft