Generating transformation semigroups using endomorphisms of preorders, graphs, and tolerances

Let Ω^Ω be the semigroup of all mappings of a countably infinite set Ω. If U and V are subsemigroups of Ω^Ω, then we write U≈V if there exists a finite subset F of Ω^Ω such that the subsemigroup generated by U and F equals that generated by V and F. The relative rank of U in Ω^Ω is the least cardinality of a subset A of Ω^Ω such that the union of U and A generates Ω^Ω. In this paper we study the notions of relative rank and the equivalence ≈ for semigroups of endomorphisms of binary relations on Ω.

The semigroups of endomorphisms of preorders, bipartite graphs, and tolerances on Ω are shown to lie in two equivalence classes under ≈. Moreover such semigroups have relative rank 0, 1, 2, or d in Ω^Ω where d is the minimum cardinality of a dominating family for NN. We give examples of preorders, bipartite graphs, and tolerances on Ω where the relative ranks of their endomorphism semigroups in Ω^Ω are 0, 1, 2, and d.

We show that the endomorphism semigroups of graphs, in general, fall into at least four classes under ≈ and that there exist graphs where the relative rank of the endomorphism semigroup is 2^ℵ0.