The monoid of the random graph

DOI10.1007/PL00006009MaRDI QIDQ1576305zbMATH OpenOpenAlexFDO

Authors Anthony Bonato, Dejan Delić

Publication date 21 March 2001

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00006009

zbMATH Keywords

countable linear orderscountable random graphsminimal idempotentsmonoids of endomorphismsposets of idempotents

Mathematics Subject Classification ID

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

Review text

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)\).

Recommendations

• Random graphs in the monadic theory of order
• On monoid graphs
• Bounded monochromatic components for random graphs
• The Grothendieck constant of random and pseudo-random graphs
• scientific article; zbMATH DE number 168429
• Graphs and ranks of monoids
• Monochromatic cycle partitions in random graphs
• The cofinality of the random graph

Cited in

(12)

• Fraïssé limits in comma categories
• Bounded monochromatic components for random graphs
• The endomorphism monoid of the random graph has uncountably many ideals.
• Minimal functions on the random graph
• Absolute graphs with prescribed endomorphism monoid
• The poset of all copies of the random graph has the 2-localization property
• A characterization of retracts in certain Fraïssé limits
• scientific article; zbMATH DE number 168429 (Why is no real title available?)
• MONOTONE INDEPENDENCE, COMB GRAPHS AND BOSE–EINSTEIN CONDENSATION
• Automorphism groups of countable algebraically closed graphs and endomorphisms of the random graph
• The random graph
• All countable monoids embed into the monoid of the infinite random graph

This page was built for publication: The monoid of the random graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1576305)