Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 381

Preprint Number 381

Previous Next Preprint server

381. Péter Pál Pach, Michael Pinsker, Gabriella Pluhár, András Pongrácz, Csába Szabó
Reducts of the random partial order

Submission date: 1 December 2011.


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

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 1111.7187: pdf, ps.

Last updated: March 23 2021 09:22 Please send your corrections to: