×

The monoid of the random graph. (English) Zbl 0957.20045

The countable random graph \(R\) is the unique graph with the property that given any two non-empty disjoint finite sets of vertices there is a vertex in neither set that is adjacent to all members of the first set but to no member of the second. This paper has as its subject \(\text{End}(R)\), the monoid of all endomorphisms of \(R\), where a morphism between graphs is a mapping that preserves adjacency.
It is proved that \(\text{End}(R)\) has no zero, is not regular, nor is it idempotent-generated. However, the cardinality of the set of minimal idempotents is that of the continuum and every countable linear order is embedded in the poset of idempotents of \(\text{End}(R)\).

MSC:

20M20 Semigroups of transformations, relations, partitions, etc.
05C80 Random graphs (graph-theoretic aspects)
06A05 Total orders
Full Text: DOI