# Exponential object in the category of simple, undirected graphs

Let $$G_i = (V_i, E_i)$$ be simple, undirected graphs for $$i=1,2$$. A graph homomorphism is a map $$f:V_1\to V_2$$ such that $$\{f(v), f(w)\}\in E_2$$ whenever $$\{v,w\}\in E_1$$.

By $$\text{Hom}(G_1, G_2)$$ we denote the collection of graph homomorphisms from $$G_1$$ to $$G_2$$. Note that it is possible that $$\text{Hom}(G_1, G_2)=\emptyset$$.

This paper is supposed to describe how we can make $$\text{Hom}(G_1, G_2)$$ into a graph - but I can't flesh out a criterion for: when do $$f, g \in \text{Hom}(G_1, G_2)$$ form an edge?

• I don't read the paper, but how about considering free groupoids $\mathcal{G}_1$, $\mathcal{G}_2$ generated by $G_1$, $G_2$ and then taking appropriate subgraph of the underlying graph of the category $\textbf{Cat}(\mathcal{G}_1,\mathcal{G}_2)$? – Slup Dec 4 '19 at 9:12
• Good point - I think that this exactly amounts to what is described in the answer below. – Dominic van der Zypen Dec 5 '19 at 13:00

The title of your question asks about "exponential object[s] in the category of simple, undirected graphs". I can tell you what they are.

(The body of your question asks about a construction in a specific paper, which I haven't read, so I can't answer that question directly. But of course, exponentials are unique when they exist.)

So: in the category of simple graphs that you mention, the exponentials $$\mathrm{HOM}(G_1, G_2)$$ are as follows. A vertex of $$\mathrm{HOM}(G_1, G_2)$$ is a graph homomorphism from $$G_1$$ to $$G_2$$. Two homomorphisms $$\phi, \psi: G_1 \to G_2$$ are adjacent in $$\mathrm{HOM}(G_1, G_2)$$ iff whenever $$x$$ and $$y$$ are adjacent vertices of $$G_1$$, then $$\phi(x)$$ and $$\psi(y)$$ are adjacent vertices of $$G_2$$.

I'd recommend Godsil and Royle's book Algebraic Graph Theory. This blog post also says more about the cartesian closed category of simple graphs.

• Thanks for the explanation and the useful link to the blog post you wrote! – Dominic van der Zypen Dec 4 '19 at 16:31

Let $$\textbf{Graph}$$ be the category of (undirected) graphs. Consider a graph $$I$$ that consists of a single edge. Note that for every graph $$G$$ there exists a bijection $$\mathrm{Hom}_{\textbf{Graph}}(I,G) \cong \mbox{ the set of edges of }G$$ natural in $$G$$. In other words the functor sending each graph to its set of edges is represented by $$I$$.

Let $$pt$$ be a graph with exactly one vertex. Then we have another natural bijection $$\mathrm{Hom}_{\textbf{Graph}}(pt,G) \cong \mbox{ the set of vertices of }G$$

Suppose that $$i_0,i_1:pt\rightarrow I$$ are two distinct morphisms (endpoints of $$I$$).

Now pick graphs $$G_1, G_2$$ and let $$\textbf{Hom}(G_1,G_2)$$ be their exponential object (we assume that it exists). Then

$$\mathrm{Hom}_{\textbf{Graph}}(G_1\times I,G_2) \cong \mathrm{Hom}_{\textbf{Graph}}\left(I,\textbf{Hom}(G_1,G_2)\right) \cong \mbox{ the set of edges of }\textbf{Hom}(G_1,G_2)$$

So each edge in $$\textbf{Hom}(G_1,G_2)$$ corresponds uniquely to a morphism of graphs $$f:G_1\times I \rightarrow G_2$$. Now you can also verify that the edge corresponding to $$f$$ has precisely $$f\cdot i_0,f\cdot i_1:G_1\cong G_1\times pt\rightarrow G_2$$ as its endpoints.

This I think recovers the answer given by Tom Leinster above.

• Thanks for this nice exposition @Slup! – Dominic van der Zypen Dec 6 '19 at 9:00
• @DominicvanderZypen I am happy that you find it useful. – Slup Dec 6 '19 at 9:08