Adjoint Functors Between Set and Graph Categories: A Categorical Comparison with Topology

Functors and Adjunctions from Set Category to Graph CategoryDefinitionsAnalogy with TopologyAdjunctions in Topology CategoryAdjunctions in Graph CategoryCategorical Product of GraphsUniversal Property

 

Functors and Adjunctions from Set Category to Graph Category

Definitions

Let us define two functors from $\mathbf{Set}$$\mathbf{Set}$ to $\mathbf{Graph}$$\mathbf{Graph}$ as follows:

• Edgeless graph functor $E$$E$: Sends a set $X$$X$ to $(X,\mathrm{\varnothing })$$(X,\emptyset)$, where $X$$X$ is the set of vertices and the edge set is empty.

• Complete graph functor $C$$C$: Sends a set $X$$X$ to $(X,E)$$(X,E)$, where $E=\{\{u,v\}:u,v\in X\}$$E=\{\{u,v\}:u,v\in X \}$.

Remark. In $\mathbf{Graph}$$\mathbf{Graph}$, for a graph $(V,E)$$(V,E)$, we allows $(x,x)\in E$$(x,x)\in E$.

Analogy with Topology

The edgeless graph sounds like trivial topology and the complete graph sounds like discrete topology.

Adjunctions in Topology Category

We know that for $\mathbf{Top}$$\mathbf{Top}$, we have the adjoint triple as follows:

$${\mathrm{Hom}}_{\mathbf{Top}}(D(X),Y)\cong {\mathrm{Hom}}_{\mathbf{Set}}(X,F(Y)),{\mathrm{Hom}}_{\mathbf{Set}}(F(Y),Z)\cong {\mathrm{Hom}}_{\mathbf{Top}}(Y,T(Z))$$

Where $D$$D$ is the discrete topology functor, $F$$F$ is the forgetful functor, and $T$$T$ is the trivial topology functor.

Adjunctions in Graph Category

For $\mathbf{Graph}$$\mathbf{Graph}$, we get a kind of opposite result. The reason is when we define the morphism in $\mathbf{Top}$$\mathbf{Top}$, we are considering the contravariant functor:

$${\mathbf{Top}}^{\mathrm{op}}\to \mathbf{Lattice},(X,\tau )⟼\tau$$

But in the category of Graph, we have:

$$\mathbf{Graph}\to \mathbf{Set},(V,E)⟼E$$

Hence the correct adjoint triple is:

$${\mathrm{Hom}}_{\mathbf{Graph}}(E(X),Y)\cong {\mathrm{Hom}}_{\mathbf{Set}}(X,F(Y)),{\mathrm{Hom}}_{\mathbf{Set}}(F(Y),Z)\cong {\mathrm{Hom}}_{\mathbf{Graph}}(Y,C(Z))$$

This result is relatively straightforward to understand, and I leave the verification to the readers.

---

Categorical Product of Graphs

Let $G=(V_G,E_G)$$G=(V_G,E_G)$ and $H=(V_H,E_H)$$H=(V_H,E_H)$ be graphs in the category of graphs "allowing self-loops". Their product graph $G\times H$$G\times H$ is defined as follows:

$$\begin{array}{rl}\text{Vertex set:}{V}_{G\times H}& =V_G\times V_H,\\ \text{Edge set:}{E}_{G\times H}& =\{\{(u,v),(u^{\prime },v^{\prime })\}|(u,u^{\prime })\in E_G\wedge (v,v^{\prime })\in E_H\}.\end{array}$$

The corresponding projection morphisms are

$${\pi }_G:G\times H⟶G,(u,v)\mapsto u,{\pi }_H:G\times H⟶H,(u,v)\mapsto v.$$

Universal Property

For any graph $K=(V_K,E_K)$$K=(V_K,E_K)$ and graph homomorphisms

$$f:K\to G,g:K\to H,$$

we define the pairing morphism

$$⟨f,g⟩:K⟶G\times H,x\mapsto (f(x),g(x)).$$

Then we have

$${\pi }_G\circ ⟨f,g⟩=f,{\pi }_H\circ ⟨f,g⟩=g,$$

and this pairing morphism is the unique homomorphism satisfying the above conditions, which confirms that $(G\times H,{\pi }_G,{\pi }_H)$$(G\times H,\pi_G,\pi_H)$ is indeed the categorical product.

Corrollay.

$$C(X\times Y)\cong C(X)\times C(Y)$$