The 42 reducts of the random ordered graph

DOI10.1112/PLMS/PDV037MaRDI QIDQ2949677zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky, Michael Pinsker, András Pongrácz

Publication date 2 October 2015

Published in Proceedings of the London Mathematical Society (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Model theory of denumerable and separable structures (03C15) Interpolation, preservation, definability (03C40) Generalized Ramsey theory (05C55) Infinite automorphism groups (20B27)

Abstract: The random ordered graph is the up to isomorphism unique countable homogeneous linearly ordered graph that embeds all finite linearly ordered graphs. We determine the reducts of the random ordered graph up to first-order interdefinability.

Recommendations

• Reducts of the random graph
• The Structure of Random Graph Orders
• Reducts of the random bipartite graph
• Reducts of random hypergraphs
• scientific article; zbMATH DE number 970794
• On retracts of the random graph and their natural order
• scientific article; zbMATH DE number 1944718
• Reducts of the random partial order

Cites work

• A survey of homogeneous structures
• Decidability of definability
• scientific article; zbMATH DE number 44603 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• Minimal functions on the random graph
• Models Without Indiscernibles
• Permutations on the random permutation
• Reducts of random hypergraphs
• Reducts of the random graph
• Reducts of the random partial order
• The 116 reducts of (ℚ, <, a)
• The partite construction and Ramsey set systems
• Transitivity of permutation groups on unordered sets

Cited in

(19)

• Infinitely many reducts of homogeneous structures
• A note on orientations of the infinite random graph
• Reducts of the random bipartite graph
• Ramsey degrees: big v. small
• Permutation groups with small orbit growth
• Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting)
• The reducts of the homogeneous binary branching C-relation
• Then-ordered graphs: A new graph class
• Reducts of the random graph
• \(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
• Permutations on the random permutation
• On the structure of random hypergraphs
• Lattice of definability (of reducts) for integers with successor
• Tractable combinations of temporal CSPs
• Functional reducts of the countable atomless Boolean algebra
• The lattice of definability: origins, recent developments, and further directions
• An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
• Reducts of the generic digraph

This page was built for publication: The 42 reducts of the random ordered graph

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