In the category of graphs, the objects $G$ are the graphs of graph theory (nodes and directed edges with multi-edges and loops allowed) and the morphisms $f: G_1 \rightarrow G_2$ associate to each edge of the $G_1$, an edge of $G_2$ and likewise with nodes. The compatibility condition is on edges, $\text{source}(f(e)) = f(\text{source}(e))$ and likewise with $\text{destination}$.

Let $A$ be the graph with two nodes connected by an edge. What does the map object $A^A$ look like?

$A^A$ must have 4 nodes, 4 edges where 1 of them is a loop. If you let $D$ be the graph with a single node and no edges, this can be shown by considering maps $A \rightarrow A^A$ which are in bijection with maps $A\times A \rightarrow A$ and maps $D \rightarrow A^A$ which in in bijection with maps $A \times D \rightarrow A$ and maps $1 \rightarrow A^A$ which are in bijection with maps $(1 \times A = A) \rightarrow A$.

Through trial and error I have produced an object which I think is $A^A$. Call the nodes $I, J, K, L$. The edges are $I \rightarrow I$, $I \rightarrow J$, $J \rightarrow K$, $K \rightarrow I$, and $L$ is by itself. My textbook has no answer key so I'm looking for confirmation and if it is correct, a simpler proof.

  • $\begingroup$ There are many variations on the notion of "graph", so the term by itself is quite ambiguous. For example, it's not clear if your graphs are directed or not, or whether you allow multiple edges between two nodes. $\endgroup$ – Derek Elkins left SE Apr 17 '17 at 5:22
  • $\begingroup$ Oh sorry about that. The graphs are directed and multiple edges are allowed as well as loops $\endgroup$ – Mark Apr 17 '17 at 5:30
  • $\begingroup$ You should edit the question to have this information. $\endgroup$ – Derek Elkins left SE Apr 17 '17 at 5:46

Directed multigraphs have a particularly simple representation categorically. They are (co)presheaves over the category with two objects and two parallel (non-identity) arrows. The category of presheaves is a topos and thus is cartesian closed, so we can just calculate what the exponent looks like.

Generally, given functors $F, G : \mathcal{C}^{op}\to\mathbf{Set}$ (i.e. presheaves over $\mathcal{C}$), the functor $F^G$ is $$F^G(C)\equiv\text{Nat}(G\times\text{Hom}(-,C),F)$$ That is, the set of natural transformations from $G\times\text{Hom}(-,C)$ to $F$. If $\mathcal{C}$ is actually itself $\mathcal{D}^{op}$, i.e. we actually had a copresheaf over $\mathcal{D}$, we get the same formula just with the $\text{Hom}$ functor swapped, i.e. $$F^G(D)\equiv\text{Nat}(G\times\text{Hom}(D,-),F)$$

For graphs, our category has two objects which I'll mnemonically label $V$ and $E$ corresponding to vertices and edges, and two parallel arrows $s,t : E \to V$ corresponding to the source and target mapping. That is, given a functor $G$, $G(V)$ will be the set of vertices of the graph, $G(E)$ will be the set of edges, and $G(s),G(t)$ will be the actual source and target mappings.

For your graph $A$, we have $A(V) = \{a,b\}$, $A(E) = 1$ ($1$ is the terminal object in $\mathbf{Set}$, i.e. an arbitrary singleton set), and $A(s), A(t) : 1 \to A(V)$, which is to say they correspond to elements of $A(V)$. In particular, $A(s) = a, A(t) = b$. The remainder is just pure calculation.

$A^A(V) = \text{Nat}(A\times\text{Hom}(V,-),A)$. A natural transformation $\tau : A\times\text{Hom}(V,-)\to A$ consists of two components $\tau_V : A(V)\times\text{Hom}(V,V)\to A(V)$ and $\tau_E : A(E)\times\text{Hom}(V,E)\to A(E)$ that satisfy the naturality condition. Now there are no arrows $V \to E$ so $\text{Hom}(V,E) = \emptyset$ and thus $\tau_E$ is the empty function. The only arrow in $\text{Hom}(V,V)$ is the identity so $\tau_V : A(V)\to A(V)$. There are four possible functions of this type, but we must restrict only to those which satisfy the naturality condition. In this case, the condition is trivial. We've established that there are four vertices for $A^A$, namely $A(V)^{A(V)}$.

Next, $A^A(E) = \text{Nat}(A\times\text{Hom}(E,-),A)$. This plays out similarly as before. $\sigma : A\times\text{Hom}(E,-)\to A$ has two components $\sigma_V$ and $\sigma_E$. $\sigma_E$ is the unique function into $1$ as $A(E)\cong 1$ (in fact we could have used this logic above as well). $\sigma_V$ is a bit more interesting as $\text{Hom}(E,V) = \{s,t\}$. There are thus $2^4$ possible functions $\sigma_V$ could be, but we need to check the naturality conditions which aren't trivial in this case. The conditions are $\sigma_V(a,s) = a$ and $\sigma_V(b,t) = b$. We can freely specify the values of $\sigma_V(a,t)$ and $\sigma_V(b,s)$ giving four possibilities.

To complete the description of $A^A$, we need the functions $A^A(s)$ and $A^A(t)$. You can work out that in this case, these function have the effect of fixing the second parameter of $\sigma_V$ to $s$ and $t$ respectively. In fact, $A^A(f)(\psi) = v \mapsto \psi(v,f)$ where $f \in \{s,t\}$. When you work it out you get a graph with 4 vertices, $0,1,2,3$ and four edges $0\to 1, 1\to 1,1\to 3,0\to 3$. So your answer wasn't correct but it was close. Using your $I,J,K,L$ you get $I\to J,J\to J,J\to K,I\to K$.

You could simplify the above calculations by separating the parts that are specific to $A^A$ from the calculations that are relevant for any $G^H$. By the above, we know that $G^H(V)=G(V)^{H(V)}$ in general. Similarly, the definition of $G^H(f)$ is completely general. It takes more effort to generalize the $G^H(E)$ case as that part leveraged details of $A$ heavily, but the general case is you have edges $\{ (\sigma_E,\sigma_V)\in G(E)^{H(E)}\times G(E)^{H(E)\times\{s,t\}}\mid\forall f\in\{s,t\}.\sigma_V(G(f)(e),f)=H(f)(\sigma_E(e))\}$.

  • $\begingroup$ Very detailed, thank you! $\endgroup$ – Mark Apr 18 '17 at 3:36

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.