On retracts of the random graph and their natural order (Q1599507)

The random graph \(R\) is the unique countable graph such that for every \(n\)-element subset \(S\) of \(V(R)\) and every subset \(T\) of \(S\), there is a vertex not in \(S\) joined to each vertex of \(T\) and to no vertex of \(S\setminus T\). A graph \(G\) is called universal if every countable graph is isomorphic to an induced subgraph of \(G\). The random graph \(R\) is universal. It is proved that the natural order on the idempotents of the endomorphism monoid of the countably infinite random graph embeds in every countable order. Moreover, a certain refinement of the natural order embeds in every countable quasi-order.