Skip to content

Research at St Andrews

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

Research output: Contribution to journalArticle


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.



Original languageEnglish
Pages (from-to)1471-1485
Number of pages15
JournalAnnals of Pure and Applied Logic
Issue number12
Publication statusPublished - Sep 2010

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Automorphism groups of countable algebraically closed graphs and endomorphisms of the random graph

    Dolinka, I., Gray, R. D., McPhee, J. D., Mitchell, J. D. & Quick, M., May 2016, In : Mathematical Proceedings of the Cambridge Philosophical Society. 160, 03, p. 437-462

    Research output: Contribution to journalArticle

  2. Generating sequences of functions

    Mitchell, J. D., Peresse, Y. & Quick, M., Mar 2007, In : Quarterly Journal of Mathematics. 58, 1, p. 71-79 9 p.

    Research output: Contribution to journalArticle

  3. GAP – Groups, Algorithms, and Programming, Version 4.10.2

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 19 Jun 2019

    Research output: Non-textual formSoftware

  4. Groups St Andrews 2017 in Birmingham

    Campbell, C. M., Parker, C. W., Quick, M., Robertson, E. F. & Roney-Dougal, C. M., Apr 2019, Cambridge University Press. 508 p. (London Mathematical Lecture Note Series 455)

    Research output: Book/ReportBook

Related by journal

  1. Some isometry groups of the Urysohn space

    Cameron, P. J. & Vershik, A. M., 1 Nov 2006, In : Annals of Pure and Applied Logic. 143, 1-3, p. 70-78 9 p.

    Research output: Contribution to journalArticle

ID: 4157941