ct.category theory - Yoneda embedding target

Various categories of graphs are presheaf categories.

The category of directed graphs is (equivalent to) presheaves on $C$, where $C$ is a category with two objects, call them $V$ and $E$, and two parallel morphisms $s, t : V to E$. If you have never seen this example, you should compute for yourself that a functor $G : C^{op} to text{Set}$ is the same thing as a directed graph. You may find this "Guided tour of the topos of graphs" illuminating.

Other categories of graphs are (almost) presheaf categories. For example, take the monoid $M$ of all endomaps $lbrace 0,1rbrace to lbrace0,1rbrace$. This is a four-element monoid whose elements are the identity $id$, two constant maps $0$ and $1$, and the "twist" map $t$. View $M$ as a category (one object, four morphisms). The presheaves on $M$ are what is sometimes called "reflexive" graphs. Since this is not apparent at first sight, let me spell it out a bit. Consider a fuctor $F : M^{op} to text{Set}$, which is the same thing as a set $S$ with a right action of $M$. The corresponding graph $G$ has as its vertices the set $V = lbrace x in S mid x cdot 0 = xrbrace$ of elements fixed by the action of the constant map $0$ (exercise: the points fixed by the constant map $0$ are the same as the points fixed by the constant map $1$). The edges of $G$ are the elements of $S$. An edge $e in S$ has as its source the vertex $e cdot 0$ and the target $e cdot 1$. But since we also have the action of the twist map $t$, the situation is symmetric: to every edge $e$ going from $e cdot 0$ to $e cdot 1$ there corresponds the opposite edge $e cdot t$ going from $(e cdot t) cdot 0 = e cdot 1$ to $(e cdot t) cdot 1 = e cdot 0$. So we are talking about symmetric graphs. Our graphs may be degenerate in the sense that an edge $e$ could be its own opposite (and then it is also a loop since $e cdot 1 = e cdot 0$). The graphs are reflexive because a homomorphism between them is allowed to "squish" edges to vertices, which is another exercise in computing natural transformations.

All of this and more (perhaps too much) can be found in:

Categories of spaces may not be generalized spaces as exemplified by directed graphs, F. William Lawvere, Revista Colombiana de Matematicas, XX (1986) 179-186. (Republished in: Reprints in Theory and Applications of Categories, No. 9 (2005) pp. 1-7)