4
$\begingroup$

The question is in the title, but let me specify what I mean by the category of graphs.

In the context of this question, the category of graphs is the category of symmetric irreflexive relations. That means, not the category of symmetric reflexive relations. That means, no loops and at most one edge between vertices.

$\endgroup$
2
  • $\begingroup$ And what do you mean by a nontrivial monad? Wouldn't operads be a source of examples? $\endgroup$ Apr 18, 2013 at 11:58
  • $\begingroup$ A trivial monad for a category $C$ is the one that arises from the adjoint pair of functors $(1_C,1_C)$. I do not understand what you mean by your second question. $\endgroup$ Apr 18, 2013 at 12:07

2 Answers 2

5
$\begingroup$

I take it morphisms $f: X \to Y$ are by definition functions that preserve the relation: if $x, x'$ are related in $X$, then $f(x), f(x')$ are related in $Y$.

It's easy to manufacture some silly examples of nontrivial monads, by finding suitable monoidal products on the category of graphs and then finding monoids with respect to that monoidal product. One such monoidal product takes the disjoint sum of two graphs. Then an example of a monoid therein is the one-point graph $1$, which carries a unique monoid structure.

The associated monad $M$ takes a graph and adjoins an isolated point to the graph, which one could regard as basepoint. If $f: X \to Y$ is a graph morphism, then $M(f)$ is the obvious basepoint preserving extension. To be precise, $M(X) = 1 + X$; the unit of the monad is the inclusion of $X$ in $1 + X$, and the multiplication $1 + 1 + X \to 1 + X$ is the identity on $X$ but identifies the two copies of $1$ as one.

$\endgroup$
2
  • $\begingroup$ I know that I am an not good at making examples but I do not understand how I could miss this one. $\endgroup$ Apr 18, 2013 at 20:19
  • 4
    $\begingroup$ Don't worry; it took me a couple of minutes to think of this (having thought of and then discarding things like the complete graph which doesn't work). More important maybe is the general technique of using monoids in monoidal categories to cook up examples of monads. $\endgroup$
    – Todd Trimble
    Apr 18, 2013 at 21:22
4
$\begingroup$

There are billions and billions of them. But it turns out I originally suggested two non-examples:

  • The non-monad which takes a graph and turns it into the complete graph on the same vertices.
  • The comonad which takes a graph and turns it into the discrete graph on the same vertices. (This example was edited after Andreas Blass made his comment.)

And two that still seem to be examples:

  • The monad which takes a graph and creates a new one with the same vertices, but connects two vertices iff there is a path between them in the original graph.
  • The monad arising from $\pi_0$: it takes a graph and returns the discrete graph whose vertices are the connected components of the original graph.
$\endgroup$
10
  • $\begingroup$ In the second example, the discrete graph on the same vertices, what is the unit of the monad? $\endgroup$ Apr 18, 2013 at 12:41
  • 1
    $\begingroup$ I'm not sure the complete graph example works. If you apply such a completion functor to the function $2 \to 1$ from the 2-element set to the 1-element set (with the discrete graph structures), where would the edge in the completion of $2$ go to? $\endgroup$
    – Todd Trimble
    Apr 18, 2013 at 13:34
  • 1
    $\begingroup$ Please, do not delete the answer. The last example is correct,I think. $\endgroup$ Apr 19, 2013 at 6:43
  • 1
    $\begingroup$ In the currently last example, sending $G$ to the discrete graph on $\pi_0(G)$, isn’t there a problem with the unit morphism — edges within each connected component have no edges to map to? $\endgroup$ Apr 28, 2013 at 3:25
  • 3
    $\begingroup$ I think this proves I am very smart. Had I been doing things randomly, at least some of these would be actual examples. It takes a special talent to produce four plausibly-sounding non-examples. $\endgroup$ Apr 28, 2013 at 13:53

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.