On Retracts of the Random Graph and Their Natural Order

 We prove that the natural order on the idempotents of the endomorphism monoid of the countably infinite random graph is -universal; that is, it embeds every countable order. We therefore extend in a strong fashion a result of 2] which showed that the natural order embeds every countable linear order. We consider a refinement of the natural order which embeds every countable quasi-order. Received 26 January 2001; in revised form 3 October 2001