Applied Algebra Seminar

York University - Fall 2002

September 30, 2002 - 4:30pm
Ross N638

Speaker: Anthony Bonato

Wilfrid Laurier University



The colouring order and the natural order on retracts



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.



Algebra Seminar Home - Fall 2002