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.

Improve this question
$\endgroup$
2
  • $\begingroup$ And what do you mean by a nontrivial monad? Wouldn't operads be a source of examples? $\endgroup$
    – David White
    Commented 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$
    – Gejza Jenča
    Commented Apr 18, 2013 at 12:07

2 Answers 2

Reset to default
6
$\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.

Improve this answer
$\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$
    – Gejza Jenča
    Commented 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
    Commented 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.
Improve this answer
$\endgroup$
10
  • $\begingroup$ In the second example, the discrete graph on the same vertices, what is the unit of the monad? $\endgroup$
    – Andreas Blass
    Commented 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
    Commented Apr 18, 2013 at 13:34
  • 1
    $\begingroup$ Please, do not delete the answer. The last example is correct,I think. $\endgroup$
    – Gejza Jenča
    Commented 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$
    – Peter LeFanu Lumsdaine
    Commented 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$
    – Andrej Bauer
    Commented Apr 28, 2013 at 13:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .