All countable monoids embed into the monoid of the infinite random graph
type: Item
instance of: scholarly article
title: All countable monoids embed into the monoid of the infinite random graph
zbMATH Open document ID: 1194.05142
author: Anthony Bonato
author: Dejan Delić
author: Igor Dolinka
published in: Discrete Mathematics
publication date: 2010-03-29T00:00:00Z
review text: From the authors summary: ``We prove that the full transformation monoid on a countably infinite set is isomorphic to a submonoid of \(\text{End}(R)\), the endomorphism monoid of the infinite random graph \(R\). Consequently, \(\text{End}(R)\) embeds each countable monoid, satisfies no nontrivial monoid identity, and has an undecidable universal theory.'' Note that the infinite random graph satisfies the existentially closed adjacency property, and it is a universal graph, i.e., each countable subgraph is isomorphic to an induced subgraph of \(R\).
reviewed by: Ulrich Knauer
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 20M20
zbMATH DE Number: 5687567
zbMATH Keywords: infinite random graph
zbMATH Keywords: graph endomorphism
zbMATH Keywords: embedding
MaRDI profile type: Publication
full work available at URL: j.disc.2009.03.018
OpenAlex ID: W2040440669
cites work: On retracts of the random graph and their natural order
cites work: The monoid of the random graph
cites work: The random graph
cites work: Q4408038
cites work: The endomorphism monoid of the random graph has uncountably many ideals.
cites work: Q5819562
cites work: Q4828516
cites work: Q4003410
cites work: Q4065528
cites work: Recursive Unsolvability of a problem of Thue
DOI: 10.1016/J.DISC.2009.03.018
description: scientific article; zbMATH DE number 5687567