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

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

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Structures preserved by primitive actions of $S_ω$

Bertalan Bodor, Manuel Bodirsky
6 citations
Logical Methods in Computer Science
Advanced Topology and Set Theory
5.63
article

Structures preserved by primitive actions of $S_ω$

Bertalan Bodor, Manuel Bodirsky
article en
6 citations

Abstract

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)$.

Logical Methods in Computer ScienceVol. Volume 22, Issue 4
European Commission, Deutsche Forschungsgemeinschaft
Openalex Percentile: Top 6%
Advanced Topology and Set Theory
5.63
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon