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$?
$\begingroup$
$\endgroup$
3
asked Nov 27, 2014 at 8:25
-
2$\begingroup$ Do you want to be specific about what you mean by "graph", or are you leaving it open-ended? $\endgroup$– Tom LeinsterCommented Nov 27, 2014 at 8:39
-
1$\begingroup$ Good point - I was referring to simple, undirected graphs ( en.wikipedia.org/wiki/Graph_%28mathematics%29 ) $\endgroup$– Dominic van der ZypenCommented Nov 27, 2014 at 12:02
-
1$\begingroup$ Are loops allowed? $\endgroup$– Anton KlyachkoCommented Nov 27, 2014 at 12:16
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
answered Nov 27, 2014 at 12:22
-
$\begingroup$ Actually, their theorem states this under some cardinality constraints: gdz.sub.uni-goettingen.de/… $\endgroup$ Commented 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$ Commented Nov 27, 2014 at 14:02
$\begingroup$
$\endgroup$
3
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.
answered Nov 27, 2014 at 13:55
-
$\begingroup$ That's fantastic Adam - thanks for your general remarks! $\endgroup$ Commented 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$ Commented 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$ Commented Nov 27, 2014 at 22:14