In Category theory for the sciences, section it is explained how a graph is a functor from an indexing category to a set. I think I understand the basic concept: Ar is mapped to a set of arrows, Ve to a set of vertices, and $src$ and $tgt$ are mapped to morphisms between these sets. This contains all the information in the graph, while being a proper functor.

Still, I am not entirely confident about my understanding of the exercises. In exercise a composition is made, where first the object from the discrete category of one element is mapped to Ve, after which the graph functor is applied: I think in this case all information in $src$, $tgt$ and Ar is lost, and we are left with only the set corresponding to Ve in the end.

In exercise a similar trick is performed: here a functor maps GrIn to the symmetric graph indexing category ($\mathcal{D}$). The way the question is phrased suggests to me that the input graph changes, but I am not sure in what way it would. I would expect Ve and Ar from GrIn to be mapped to Ve and Ar in $\mathcal{D}$, and similarly for $src$ and $tgt$, with nothing being mapped to $\rho$.

In the same manner of reasoning as in the first exercise, I would think that we lose the info on $\rho$ (so no morphism comes out of the functor which maps an arrow to its reverse arrow) but with no further effect on the structure of the graph (since the full set of arrows is still in the image of Ar).

For example, with the simple graph $1 \rightleftharpoons 2$ with arrows $a$ and $b$ I would expect the following functor from $\mathcal{D}$ to Set:

$F(Ve) = \{1, 2\}$ ; $F(Ar) = \{a, b\}$

$F(src)(a) = 1$ ; $F(tgt)(a) = 2$

$F(src)(b) = 2$ ; $F(tgt)(b) = 1$

$F(\rho)(a) = b$ ; $F(\rho)(b) = a$

This matches with the described composition rules, e.g. $src \circ rho = tgt$, for example $src(rho(a)) = tgt(a)$.

Then, taking $\rho$ out of the picture, the connectivity of the graph remains the same, right? Is my reasoning correct and do I understand the mechanism behind the graph indexing categories, or am I making a mistake somewhere?

  • $\begingroup$ It may help to consider Example on category-theory.mitpress.mit.edu/chapter005.html and which immediately follows the same exercise ( in the pdf version of the book. $\endgroup$ – Tris Nefzger Jul 9 '15 at 3:02
  • 1
    $\begingroup$ "The way the question is phrased suggests to me that the input graph changes, but I am not sure in what way it would": It does not really change, other than forgetting about its symmetry. Keep in mind that you are transforming a symmetric graph into a graph, not the other way round. (There are ways to transform a graph into a symmetric graph, but these are not given by composition with a functor $\mathcal{D}\to\mathbf{GrIn}$.) $\endgroup$ – darij grinberg Jul 18 '15 at 17:56
  • 1
    $\begingroup$ I think this is what you are saying, actually. Yes, the connectivity of the graph remains the same. Your example is correct: the graph $F \circ i$ is essentially just $F$ without $F(\rho)$. $\endgroup$ – darij grinberg Jul 18 '15 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.