# 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, 2019 at 9:12
• Good point - I think that this exactly amounts to what is described in the answer below. Dec 5, 2019 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 function from the set of vertices of $$G_1$$ to the set of vertices of $$G_2$$. Two vertices $$\phi, \psi$$ of $$\mathrm{HOM}(G_1, G_2)$$ are adjacent 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! Dec 4, 2019 at 16:31
• As a point of clarification: In your answer you say that vertices are graph homomorphisms, but the post you link says that a vertex is any function on the underlying sets. Sep 4, 2020 at 8:51
• Oops! Corrected now. Thanks. Sep 18, 2020 at 18:57
• This graph is also not simple in the standard meaning of this term in graph theory, as those maps which are graph homomorphisms have loops on them. Sep 18, 2020 at 23:24

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! Dec 6, 2019 at 9:00
• @DominicvanderZypen I am happy that you find it useful.
– Slup
Dec 6, 2019 at 9:08