Algebra Seminar talk
2013-06-14
Michael Pinsker
The 42 reducts of the random ordered graph
Abstract:
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)