Generating transformation semigroups using endomorphisms of preorders, graphs, and tolerances. (Q636382)

Let \(U\) and \(V\) be subsemigroups of \(X^X\), where \(X\) is a countably infinite set; say that \(U\sim V\) if the union of \(U\) and \(F\) generates the same subsemigroup as that of \(V\) and \(F\) for some finite subset \(F\) of \(X^X\). The relative rank of \(U\) is the least cardinal of a subset \(A\) of \(X^X\) such that the union of \(U\) and \(A\) generates the whole of \(X^X\). The semigroups of endomorphisms of pre-orders, bipartite graphs and tolerances (binary relations that are reflexive and symmetric) are shown to lie in two equivalence classes under \(\sim\). These semigroups have relative ranks of 0, 1, 2 or \(d\) in \(X^X\) where \(d\) is the minimum cardinality of a so-called dominating family for \(N^N\). The authors show that endomorphism semigroups of graphs, in general, fall into at least four classes under \(\sim\) and that there exist graphs where the relative rank of the endomorphism semigroup is the cardinal of the continuum.