Algebra Seminar talk
2009-06-05
Michael Pinsker
All reducts of the random graph are model-complete
Abstract:
We consider functions acting on the random graph. More specifically,
we are interested in (topologically) closed transformation monoids and
closed permutation groups which contain the automorphism group Aut(G)
of the random graph. With the help of the Nesetril-Rödl
theorem which states that the set of finite ordered structures of a
given signature forms a Ramsey class, one can find well-behaved parts
in any mapping on the random graph. We did so and proved:
Every closed transformation monoid which contains Aut(G) either contains one of three very primitive functions which I will define in my talk, or is a "disguised group" in the sense that it is generated by the largest group which it contains. For the latter case there are precisely five possibilities, i.e., there exist five closed permutations groups which contain Aut(G). (The group case had already been shown by Simon Thomas, using different tools.)
Monoids (groups) containing Aut(G) correspond to reducts of the random graph, i.e., to structures with a first-order definition in the random graph, in a natural way. By means of this correspondence, properties of these monoids (groups) translate into properties of reducts. Our theorem allows for some model-theoretic corollaries which exploit this correspondence, one of them being: All reducts of the random graph are model-complete.