5
$\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$
3
  • 1
    $\begingroup$ Which forgetful functor do you have in mind? There are a couple of different natural functors from $\mathbf{Grph}$ to $\mathbf{Set}$. $\endgroup$ Commented Mar 14, 2020 at 7:28
  • $\begingroup$ Any one, but the one I had in mind was the one assigning a graph its underlying vertex set. $\endgroup$ Commented Mar 14, 2020 at 7:31
  • 1
    $\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$ Commented Mar 14, 2020 at 7:48

1 Answer 1

8
$\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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .