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$
3

2 Answers 2

10
$\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.

$\endgroup$
2
  • $\begingroup$ Actually, their theorem states this under some cardinality constraints: gdz.sub.uni-goettingen.de/… $\endgroup$ Nov 27, 2014 at 13:03
  • $\begingroup$ @AntonKlyachko yes, but later these constraints have been removed. In fact much more general results were proved. $\endgroup$ Nov 27, 2014 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.

$\endgroup$
3
  • $\begingroup$ That's fantastic Adam - thanks for your general remarks! $\endgroup$ Nov 27, 2014 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$ Nov 27, 2014 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$ Nov 27, 2014 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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