Reducts of the random partial order

DOI10.1016/J.AIM.2014.08.008zbMATH Open1403.03053arXiv1111.7109OpenAlexW1998637047MaRDI QIDQ462283FDOQ462283

Authors: Péter Pál Pach, Michael Pinsker, Gabriella Pluhár, András Pongrácz, Csaba Szabó 

Publication date: 20 October 2014

Published in: Advances in Mathematics (Search for Journal in Brave)

Abstract: We determine, up to the equivalence of first-order interdefinability, all structures which are first-order definable in the random partial order. It turns out that these structures fall into precisely five equivalence classes. We achieve this result by showing that there exist exactly five closed permutation groups which contain the automorphism group of the random partial order, and thus expose all symmetries of this structure. Our classification lines up with previous similar classifications, such as the structures definable in the random graph or the order of the rationals; it also provides further evidence for a conjecture due to Simon Thomas which states that the number of structures definable in a homogeneous structure in a finite relational language is, up to first-order interdefinability, always finite. The method we employ is based on a Ramsey-theoretic analysis of functions acting on the random partial order, which allows us to find patterns in such functions and make them accessible to finite combinatorial arguments.

Full work available at URL: https://arxiv.org/abs/1111.7109

Recommendations

• The 42 reducts of the random ordered graph
• Minimal functions on the random graph
• Reducts of Ramsey structures
• Reducts of random hypergraphs
• scientific article; zbMATH DE number 1045974

zbMATH Keywords

automorphism grouphomogeneous structurerandom partial ordercanonical functionRamsey expansionreduct

Mathematics Subject Classification ID

Partial orders, general (06A06) Model-theoretic algebra (03C60) Interpolation, preservation, definability (03C40) Infinite automorphism groups (20B27)

Cites Work

• Transitivity of permutation groups on unordered sets
• Schaefer's theorem for graphs
• The reducts of equality up to primitive positive interdefinability
• The complexity of temporal constraint satisfaction problems
• Title not available (Why is that?)
• Decidability of Definability
• Minimal functions on the random graph
• A survey of homogeneous structures
• Reducts of Ramsey structures
• Reducts of random hypergraphs
• A new operation on partially ordered sets.
• The 116 reducts of (ℚ, <, a)
• Reducts of the random graph
• Title not available (Why is that?)

Cited In (19)

• Partial ordering of degrees of alternative m-reducibility
• Permutation groups containing infinite symplectic linear groups and reducts of linear spaces over the two element field
• Infinitely many reducts of homogeneous structures
• On methods for generating random partial orders
• The 42 reducts of the random ordered graph
• Functional reducts of the countable atomless Boolean algebra
• Linear extensions of a random partial order
• Ramsey degrees: big v. small
• Permutation groups with small orbit growth
• REDUCTS OF STRUCTURES AND MAXIMAL-CLOSED PERMUTATION GROUPS
• THE REDUCTS OF THE HOMOGENEOUS BINARY BRANCHING C-RELATION
• The Behavior of Random Reduced Bases
• An algebraic view on p-admissible concrete domains for lightweight description logics
• Reducts of the generic digraph
• Title not available (Why is that?)
• Using model theory to find decidable and tractable description logics with concrete domains
• Reducts of Ramsey structures
• Permutations on the random permutation
• PAIRWISE NONISOMORPHIC MAXIMAL-CLOSED SUBGROUPS OF SYM(ℕ) VIA THE CLASSIFICATION OF THE REDUCTS OF THE HENSON DIGRAPHS

This page was built for publication: Reducts of the random partial order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q462283)