Exponential object in the category of simple, undirected graphs

Question

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?

Answer 1

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.

Answer 2

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.