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$
2
  • 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$ Dec 5 '19 at 13:00
8
$\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 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.

$\endgroup$
4
  • 1
    $\begingroup$ Thanks for the explanation and the useful link to the blog post you wrote! $\endgroup$ Dec 4 '19 at 16:31
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 4 '20 at 8:51
  • $\begingroup$ Oops! Corrected now. Thanks. $\endgroup$ Sep 18 '20 at 18:57
  • $\begingroup$ 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. $\endgroup$
    – lambda
    Sep 18 '20 at 23:24
6
$\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.

$\endgroup$
2
  • $\begingroup$ Thanks for this nice exposition @Slup! $\endgroup$ 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.