6
$\begingroup$

This question relates to Realizing groups as automorphism groups of graphs.

Given a monoid $M$, is there a graph $G$ such that the endomorphism monoid $\textrm{End}(G)$ is isomorphic to $M$?

$\endgroup$
9
$\begingroup$

Hedrlín and Pultr proved that every monoid was the endomorphism monoid of a graph. See their paper "Symmetric relations (undirected graphs) with given semigroup" Monatsh. Math 69 (1965), eudml, DOI: 10.1007/BF01297617.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Actually, their theorem states this under some cardinality constraints: gdz.sub.uni-goettingen.de/… $\endgroup$ – Anton Klyachko Nov 27 '14 at 13:03
  • $\begingroup$ @AntonKlyachko yes, but later these constraints have been removed. In fact much more general results were proved. $\endgroup$ – Adam Przeździecki Nov 27 '14 at 14:02
12
$\begingroup$

Trying to forestall another question along these lines let me add that every locally presentable category fully embeds into the category of graphs - see Adámek, Rosický Locally presentable and accessible categories 1994.

In fact, depending on set theories in which we work, every concrete category fully embeds into graphs - see Pultr, Trnková, Combinatorial, algebraic and topological representations of groups, semigroups and categories 1980.

For example: the category of metrizable spaces embeds into Graphs and in some set theories the category of Hausdorff topological spaces also embeds into Graphs.

Monoid is a category with a single object, hence a special case of the first result.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That's fantastic Adam - thanks for your general remarks! $\endgroup$ – Dominic van der Zypen Nov 27 '14 at 14:17
  • 1
    $\begingroup$ To add some info on Adam's remarks: for Adámek and Rosický, a graph is a set endowed with a binary relation and a homomorphism is a function preserving the binary relation. More concretely put, their graphs are directed, can have loops but cannot have multiple edges, and may be infinite. They give that definition on p.10. The section on embedding into graphs, which presumably contains the results Adam mentions, is section 2.G. $\endgroup$ – Tom Leinster Nov 27 '14 at 18:32
  • $\begingroup$ If the category-theoretic setting is any similar to the many other contexts where the encode-arbitrary-structures-as-graphs idea occurs, I would expect that you can do the same with simple undirected graphs. By transitivity, it would be enough to show that the category of directed graphs fully embeds into the category of undirected graphs. $\endgroup$ – Emil Jeřábek Nov 27 '14 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.