4
$\begingroup$

Let $\mathrm{Graph}$ be the category of simple, undirected graphs with graph homomorphisms. For any graphs $G, H$ we denote by $\text{Hom}(G, H)$ the set of graph homomorphisms $f:G\to H$. (Note that $\text{Hom}(G, H)$ can be empty, for instance if $\chi(G) > \chi(H)$.)

We can make $\text{Hom}(G, H)$ into a graph by saying that $f, g: G\to H$ form an edge if and only if $\{f(v), g(v)\}\in E(H)$ for all $v\in V(G)$.

Is $\mathrm{Graph}$ cartesian-closed?

$\endgroup$
  • 2
    $\begingroup$ This category lacks a terminal object. $\endgroup$ – Wojowu Jan 28 at 15:24
  • 1
    $\begingroup$ @TimCampion A simple graph by definition has no loops. $\endgroup$ – Wojowu Jan 28 at 15:36
  • 1
    $\begingroup$ Further, I'm afraid the obviously defined evaluation morphism is not a homomorphism, at least not for your definition of $Hom$ - if I'm not mistaken, the products in this category are defined as: $(v_1,w_1),(v_2,w_2)$ are connected in $G\times H$ iff $v_1,v_2$ are connected in $G$ and $w_1,w_2$ are connected in $H$. Applying this to $Hom(G,H)\times G$, we have edges between $(f,v)$ and $(g,w)$, and it won't necessarily be the case $f(v)$ and $g(w)$ are connected. $\endgroup$ – Wojowu Jan 28 at 15:46
  • 1
    $\begingroup$ It also makes sense to point out that two related categories, that of directed graphs and undirected graphs (not necessarily simple) are cartesian closed because they are Grothendieck toposes by virtue of being categories of presheaves on a small category. $\endgroup$ – Dmitri Pavlov Jan 28 at 16:17
  • 1
    $\begingroup$ There has been some discussion on the n-Category Café about this here and here. $\endgroup$ – Tobias Fritz Jan 28 at 16:33
8
$\begingroup$

There are many categories of graphs, so perhaps it's best to take a synoptic view.

The table below surveys several categories of directed graphs (DG), directed multigraphs (DM), undirected graphs (UG), and undirected multigraphs (UM). The asterisks indicate the ones which are not cartesian closed, in each case lacking a terminal object.

\begin{array}{lcccc} & DG & DM & UG & UM \\ \text{Loops allowed} & 10 & 2 & 12 & 3\\ \text{Loops allowed and reflexive} & 9 & 1 & 11 & 4\\ \text{Loops allowed and strictly reflexive} & 9 & 7 & 11 & 8 \\ \text{Loops not allowed} & 13* & 5* & 14* & 6* \end{array} The concepts of reflexive and strictly reflexive graphs are distinct for multigraphs, but the same for graphs, which is why numbers 9 and 11 are duplicated in the table.

  • (1) For a category theorist, the default category of graphs to use is the category of reflexive, directed multigraphs where loops are allowed. In this category, from a vertex $v$ to a vertex $w$ there is a set of edges $E(v,w)$ (the "multi" part), there is no relationship between $E(v,w)$ and $E(w,v)$ (the "directed" part), for every vertex $v$ there is a distinguished edge $i_v \in E(v,v)$ (the "reflexive" part) and there are no other restrictions on $E(v,v)$ ("loops are allowed"). A morphism $f$ is a map of vertex sets and a map of edge sets preserving incidence relations and such that $f(i_v) = i_{f(v)}$. This category is cartesian closed -- in fact it can be described as the functor category $\mathcal{R}^{op} \to Set$ where $\mathcal{R}$ is (a skeleton of) the category of linearly ordered sets of cardinality 1 or 2 (this category has 2 objects and 5 nonidentity morphisms).

    (As observed by Dmitri Pavolov above, a category of functors into $Set$ is always cartesian closed).

  • (2) A variation is the category of directed multigraphs where loops are allowed. This is similar to the previous category, but we drop the distinguished vertices $i(v)$. This category is also cartesian closed -- it is the category of functors $\mathcal I^{op} \to Set$ where $\mathcal I$ is (a skeleton of) the category of linearly ordered sets of cardinality 1 or 2 and injective homomorphisms (this category has two objects and two nonidentity maps).

  • (3) Another variation is the category of undirected multigraphs where loops are allowed. This is similar to the previous category, but there is a specified bijection between $E(v,w)$ and $E(w,v)$ which must be preserved by morphisms (and this bijection is the identity when $v=w$). This is cartesian closed -- it is the category of functors $\mathcal U^{op} \to Set$ where $\mathcal U$ is (a skeleton of) the category of sets of cardinality 1 or 2 and injective maps (this category has 2 objects and 3 nonidentity morphisms).

  • (4) Another variation is the category of reflexive undirected multigraphs where loops are allowed. This is like the previous category, but we add back the distinguished loops $i(v)$. This category is cartesian closed; it is the functor category $\mathcal T^{op} \to Set$ where $\mathcal T$ is (a skeleton of) the category of sets of cardinality 1 or 2 (this category has 2 objects and 6 nonidentity morphisms).

  • (5) The category of directed multigraphs where loops are not allowed is not cartesian closed. It doesn't have a terminal object.

  • (6) Similarly, the category of undirected multigraphs where loops are not allowed is not cartesian closed because it doesn't have a terminal object.

  • (7) The category of strictly reflexive directed multigraphs consists of reflexive directed multigraphs satisfying $e \in E(v,v) \Rightarrow e = i(v)$ (the objects may equivalently be thought of as directed loop-free multigraphs, with slightly more homomorphisms). This category is localization of reflexive directed multigraphs, and it can be checked that the localization induces a cartesian closed structure.

  • (8) Similar comments apply to strictly reflexive undirected multigraphs.

Moving away from multigraphs,

  • (9) Consider category of directed reflexive graphs where loops are allowed. This category is a localization of the multigraph version, and it can be checked that the localization induces a cartesian closed structure. Similarly, (10) directed graphs where loops are allowed, (11) undirected reflexive graphs where loops are allowed, and (12) undirected graphs where loops are allowed are cartesian closed, with the cartesian closed structure induced by localization from the multigraph version. Note that in particular an undirected reflexive graph is equivalent to a simple graph, with a few more morphisms in the category.

  • (13) The category of directed loop-free graphs is not cartesian closed, and nor is the category of (14) undirected loop-free graphs. They fail to have terminal objects, as Wojowu observed.

I think Wojowu's further observations are also spot-on, to the effect that the failure of cartesian closedness is not just some technicality about terminal objects. Rather, in order to have cartesian closedness, it is essential to allow morphisms that collapse an edge to a point. The "naive" definition of morphism of simple graphs does not allow this; we must add such morphisms. A slick way to do this is to just pretend for the purposes of morphisms that there is a loop at every point.

$\endgroup$
  • 1
    $\begingroup$ Lovely answer, but one terminological quibble. You write “For a category theorist, the default category of graphs to use is the category of reflexive, directed multigraphs where loops are allowed.” — really? In my (mostly category-theoretic) experience, these are always called reflexive graphs, and unqualified graphs means these without the reflexivity, i.e. the second definition you give. $\endgroup$ – Peter LeFanu Lumsdaine Jan 28 at 16:30
  • 2
    $\begingroup$ @PeterLeFanuLumsdaine I agree; in my entire experience of category theory unqualified "graph" always means the non-reflexive version, and I very much disagree that this is just because it's easier to define. Non-reflexive graphs are much more natural as, for instance, the domain of the monad for free categories. In some cases this can have serious mathematical consequences, e.g. arxiv.org/abs/0907.3961. $\endgroup$ – Mike Shulman Jan 28 at 17:46
  • 1
    $\begingroup$ Which isn't to say that we never use reflexive graphs; the point is terminological. $\endgroup$ – Mike Shulman Jan 28 at 17:47
  • 1
    $\begingroup$ @MikeShulman Interesting! In fact, the domain of the free category monad was actually something I had in mind when thinking that reflexive graphs where more natural! For instance, in simplicial localization it's the adjunction with reflexive graphs that's used. $\endgroup$ – Tim Campion Jan 28 at 17:49
  • 3
    $\begingroup$ @TimCampion A classic distinction between these two categories as toposes was made by Lawvere in this short paper. And to bring out Mike's example: the free category monad on the category of non-reflexive graphs is a cartesian monad, but this is not so over reflexive graphs (since the underlying functor doesn't preserve pullbacks). $\endgroup$ – Alexander Campbell Jan 28 at 23:33

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.