Reducts of Ramsey structures
From MaRDI portal
Abstract: One way of studying a relational structure is to investigate functions which are related to that structure and which leave certain aspects of the structure invariant. Examples are the automorphism group, the self-embedding monoid, the endomorphism monoid, or the polymorphism clone of a structure. Such functions can be particularly well understood when the relational structure is countably infinite and has a first-order definition in another relational structure which has a finite language, is totally ordered and homogeneous, and has the Ramsey property. This is because in this situation, Ramsey theory provides the combinatorial tool for analyzing these functions -- in a certain sense, it allows to represent such functions by functions on finite sets. This is a survey of results in model theory and theoretical computer science obtained recently by the authors in this context. In model theory, we approach the problem of classifying the reducts of countably infinite ordered homogeneous Ramsey structures in a finite language, and certain decidability questions connected with such reducts. In theoretical computer science, we use the same combinatorial methods in order to classify the computational complexity for various classes of infinite-domain constraint satisfaction problems. While the first set of applications is obviously of an infinitary character, the second set concerns genuinely finitary problems -- their unifying feature is that the same tools from Ramsey theory are used in their solution.
Recommendations
Cited in
(32)- Infinitely many reducts of homogeneous structures
- The wonderland of reflections
- Minimal functions on the random graph
- Permutation groups with small orbit growth
- Ramsey transfer to semi-retractions
- Binary simple homogeneous structures are supersimple with finite rank
- The affine and projective groups are maximal
- Reconstructing the topology of clones
- On (uniform) hierarchical decompositions of finite structures and model-theoretic geometry
- scientific article; zbMATH DE number 6500579 (Why is no real title available?)
- New Ramsey classes from old
- \(2^{\aleph_{0}}\) pairwise nonisomorphic maximal-closed subgroups of \(\mathrm{Sym}(\mathbb N)\) via the classification of the reducts of the Henson digraphs
- Reducts of the random partial order
- On constraints and dividing in ternary homogeneous structures
- Permutations on the random permutation
- Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
- PROJECTIVE CLONE HOMOMORPHISMS
- CORES OVER RAMSEY STRUCTURES
- Homogeneous 1-based structures and interpretability in random structures
- Solving equation systems in ω-categorical algebras
- Pseudo‐loop conditions
- Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
- Constraint satisfaction problems for reducts of homogeneous graphs
- Reducts of the Henson graphs with a constant
- Functional reducts of the countable atomless Boolean algebra
- On the descriptive complexity of temporal constraint satisfaction problems
- The isomorphism problem for oligomorphic groups with weak elimination of imaginaries
- Smooth approximations and CSPs over finitely bounded homogeneous structures
- Smooth approximations: an algebraic approach to CSPs over finitely bounded homogeneous structures
- A complexity dichotomy in spatial reasoning via Ramsey theory
- Reducts of the generic digraph
- A Ramsey theorem for structures with both relations and functions
This page was built for publication: Reducts of Ramsey structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3118392)
