As the title says, I've been interested for a while in seeing if the assignment End(G) for directed graphs G can be made functorial, for some not-so-obvious choice of mapping for the corresponding morphisms. If not, why?
5
-
2$\begingroup$ You can usually achieve this sort of thing by just sending all the non-isomorphisms to trivial morphisms, but that's probably not what you want. $\endgroup$– Dave BensonCommented Aug 25, 2023 at 21:06
-
4$\begingroup$ @DaveBenson: Sadly that doesn’t usually work, since it doesn’t preserve identities, and if you say “…send non-identities to trivial maps, and identities to identities”, then it no longer preserves composition. $\endgroup$– Peter LeFanu LumsdaineCommented Aug 25, 2023 at 21:45
-
$\begingroup$ @PeterLeFanuLumsdaine What is a trivial morphism if not an identity map? $\endgroup$– Alec RheaCommented Aug 26, 2023 at 7:05
-
4$\begingroup$ @AlecRhea: I presume @ DaveBenson meant “trivial map”in the sense of “zero map”, i.e. “constant map with value the unit of the target monoid” — the obvious (and I think only) way to naturally get a map between any two arbitrary monoids. $\endgroup$– Peter LeFanu LumsdaineCommented Aug 26, 2023 at 7:14
-
$\begingroup$ Indeed. What I suggested is naïve and doesn't work. $\endgroup$– Dave BensonCommented Aug 26, 2023 at 13:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
No, this isn’t possible. If $\newcommand{\End}{\mathrm{End}}\newcommand{\Aut}{\mathrm{Aut}}\End(-)$ extended to a functor on arbitrary maps of graphs, that would imply that whenever $G$ embeds as a retract of $H$, then $\End(G)$ embeds as a retract of $\End(H)$, and (restricting to invertible elements) $\Aut(G)$ as a retract of $\Aut(H)$. But take $G$ to consist of three vertices each with a single loop, and $H$ to be $G$ with a second loop added at one of the vertices. Then $G$ is evidently a retract of $H$, but $\Aut(G)$ is $S_3$, while $\Aut(H)$ is $C_2 \times C_2$, so $\Aut(G)$ doesn’t embed into $\Aut(H)$.
Edit: Keith Kearnes points out a simpler counterexample in comments — the discrete graphs on 3 and 5 vertices respectively, with automorphism groups $S_3$ and $S_5$. These show that $\End$ and $\Aut$ are “unfunctorialisable” already on $\mathrm{Set}$, and hence on any category admitting a full embedding from $\mathrm{Set}$ — hence, in particular, on directed graphs.
Retractions are often useful as elementary obstructions for this sort of problem (see here for another example), since they’re preserved by arbitrary functors, and in many familiar categories, they’re quite easy both to construct examples of, and to rule out when they don’t exist.
answered Aug 26, 2023 at 12:57
-
6$\begingroup$ It might be slightly simpler to let $G$ be a discrete graph on $3$ vertices and $H$ be a discrete graph on $5$ vertices. It is easy to see that $\textrm{Aut}(G)\cong S_3$ and $\textrm{Aut}(H)\cong S_5$, and the former is not a retract of the latter. $\endgroup$ Commented Aug 26, 2023 at 13:04
-
6$\begingroup$ @KeithKearnes: Of course, very nice! And that example shows that $\mathrm{End}(-)$ is “unfunctorialisable” not just on graphs, but already on plain sets. $\endgroup$ Commented Aug 26, 2023 at 13:06