| If G and H are graphs, then G \preceq H if there is an
edge-preserving vertex-mapping, or homomorphism, from G
to H. The quasi-order relation \preceq on the class of finite
graphs gives rise to an order relation in a natural way, called
the colouring order, written C. The order
C has many intriguing properties; for example,
Hedrlin proved in the 1960's that it is universal:
every countable order embeds in C as a suborder.
Hedrlin's proof is long and makes heavy use of category
theory. In a recent tour de force, Nesetril discovered a
shorter combinatorial proof of Hedrlin's theorem.
A retract of a graph is an endomorphism f that is
idempotent: f^2=f. Retracts of graphs and other structures have
been widely studied in semigroup theory, going back to Howie's
pioneering work on the idempotents of the full transformation
semigroup. The natural order on retracts is defined by
f \le g if fg=gf=f. While the natural order is a familiar tool
in algebraic semigroup theory, it has only recently attracted the
attention of the graph homomorphism community.
After giving some background on the colouring order C
and the natural order, we will see how these two orders are
related. In particular, we will prove that the natural order on
the retracts of the infinite random graph embeds C and
so is universal.
|