The 42 reducts of the random ordered graph

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.

42 pages (!)

Cited by in corpus (2)

• Infinitely many reducts of homogeneous structures
• Twenty years of Nešetřil's classification programme of Ramsey classes