Algebra Seminar talk

Michael Pinsker
The 42 reducts of the random ordered graph

The random ordered graph is the up to isomorphism unique countable homogeneous structure that embeds all finite linearly ordered graphs. I will present a complete classification of all structures which have a first order definition in the random ordered graph.

This classification includes in particular all structures definable in the order of the rationals (previously classified by Cameron '76), the random graph (Thomas '91) and the random tournament (Bennett '97). We obtained the result by the recent method of canonical functions, which is based on structural Ramsey theory and which I will outline.

(Joint work with M. Bodirsky and A. Pongrácz)