4
$\begingroup$

Often forgetful functors from a category $\mathbf{C}$ of algebraic objects to $\mathbf{Set}$ have a left adjoint, which gives a "free construction" of a $\mathbf{C}$-object on any set $X$.

What about the forgetful functor from the category of simple graphs $\mathbf{Gph}$ - does this have a left adjoint? This would presumably give a construction of a "free graph" on a set.

Are there any other categories of "relational structures" (e.g. posets, directed graphs) where the forgetful functor has a left adjoint?

$\endgroup$
  • $\begingroup$ Which forgetful functor do you have in mind? There are a couple of different natural functors from $\mathbf{Grph}$ to $\mathbf{Set}$. $\endgroup$ – Malice Vidrine Mar 14 at 7:28
  • $\begingroup$ Any one, but the one I had in mind was the one assigning a graph its underlying vertex set. $\endgroup$ – Jordan Mitchell Barrett Mar 14 at 7:31
  • $\begingroup$ I'm pretty sure a left adjoint to that one is just the functor taking a set $X$ to the graph with vertex set $X$ and no edges. I can't recall if the connected components functor on simple graphs has a left adjoint, though... $\endgroup$ – Malice Vidrine Mar 14 at 7:48
6
$\begingroup$

Whenever I say graph in this answer, I mean simple graph.

We need to be a bit more precise here, and specify what the arrows are in $\mathbf{Gph}$. A natural choice would be maps $f: G \to G'$ between the vertex sets such that if there is an edge between $x,y \in G$ (which I will denote by $E(x, y)$), then there is an edge between $f(x)$ and $f(y)$. In this case the forgetful functor $U: \mathbf{Gph} \to \mathbf{Set}$, which sends a graph to its underlying vertex set, does indeed have a left adjoint.

The construction was already mentioned by Malice Vidrine in the comments. We can define $F: \mathbf{Set} \to \mathbf{Gph}$ by sending a set $X$ to the graph $F(X)$ with vertex set $X$ and no edges. A function $f: X \to Y$ of sets is then also an arrow $f: F(X) \to F(Y)$ in $\mathbf{Gph}$, so we just set $F(f) = f$.

Let $X$ be a set and $G$ be a graph. Then a function $X \to U(G)$ is literally the same thing as a morphism of graphs $F(X) \to G$. So $\operatorname{Hom}(X, U(G)) = \operatorname{Hom}(F(X), G)$, which is definitely natural, so $F$ is left adjoint to $G$.


In fact, $F: \mathbf{Set} \to \mathbf{Gph}$ itself has again a left adjoint $C: \mathbf{Gph} \to \mathbf{Set}$. Here $C$ is the connected components functor. So it takes a graph $G$ to the set of connected components of $G$. It is a good exercise to define $C$ on the arrows in $\mathbf{Gph}$ and to check that it is indeed left adjoint to $F$.

| cite | improve this answer | |
$\endgroup$

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.