2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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)$? $\endgroup$ – Slup Dec 4 '19 at 9:12
  • $\begingroup$ Good point - I think that this exactly amounts to what is described in the answer below. $\endgroup$ – Dominic van der Zypen Dec 5 '19 at 13:00
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks for the explanation and the useful link to the blog post you wrote! $\endgroup$ – Dominic van der Zypen Dec 4 '19 at 16:31
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for this nice exposition @Slup! $\endgroup$ – Dominic van der Zypen Dec 6 '19 at 9:00
  • 1
    $\begingroup$ @DominicvanderZypen I am happy that you find it useful. $\endgroup$ – Slup Dec 6 '19 at 9:08

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.