dc.contributor.author | Mitchell, James D. | |
dc.contributor.author | Morayne, Michal | |
dc.contributor.author | Peresse, Yann | |
dc.contributor.author | Quick, Martyn | |
dc.date.accessioned | 2017-04-20T08:32:03Z | |
dc.date.available | 2017-04-20T08:32:03Z | |
dc.date.issued | 2010-09-01 | |
dc.identifier.citation | Mitchell , J D , Morayne , M , Peresse , Y & Quick , M 2010 , ' Generating transformation semigroups using endomorphisms of preorders, graphs, and tolerances ' , Annals of Pure and Applied Logic , vol. 161 , no. 12 , pp. 1471-1485 . https://doi.org/10.1016/j.apal.2010.05.001 | |
dc.identifier.issn | 0168-0072 | |
dc.identifier.other | PURE: 10301492 | |
dc.identifier.other | PURE UUID: c526c92c-43ae-43e3-86d2-b1ee8e2c0597 | |
dc.identifier.other | Scopus: 77955511177 | |
dc.identifier.uri | http://hdl.handle.net/2299/17974 | |
dc.description | J. D. Mitchell, M. Morayne, Y. Peresse, and M. Quick, 'Generating transformation semigroups using endomorphisms of preorders, graphs, and tolerances', Annals of Pure and Applied Logic, Vol. 161 (12): 1471-1485, first published online 9 June 2010. The version of record is available online at doi:10.1016/j.apal.2010.05.001. Published by Elsevier. © 2010 Elsevier B. V. | |
dc.description.abstract | 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. | en |
dc.format.extent | 15 | |
dc.language.iso | eng | |
dc.relation.ispartof | Annals of Pure and Applied Logic | |
dc.subject | SEMIGROUPS | |
dc.subject | Infinite Combinatorics | |
dc.subject | graph theory | |
dc.title | Generating transformation semigroups using endomorphisms of preorders, graphs, and tolerances | en |
dc.contributor.institution | Mathematics and Theoretical Physics | |
dc.contributor.institution | School of Physics, Engineering & Computer Science | |
dc.contributor.institution | Department of Physics, Astronomy and Mathematics | |
dc.description.status | Peer reviewed | |
rioxxterms.versionofrecord | https://doi.org/10.1016/j.apal.2010.05.001 | |
rioxxterms.type | Journal Article/Review | |
herts.preservation.rarelyaccessed | true | |