Category Theory – Strongly Connected Components as Adjoint Functor

ct.category-theorygraph theory

Fix a faithful functor $\Gamma: \mathsf C\longrightarrow \mathsf{Set}$ and think of it as the "underlying points". When it exists, a left adjoint $\mathrm{disc}\dashv \Gamma$ can be thought of as the "discrete objects" functor. When it exists, a further left adjoint $\pi_0\dashv \mathrm{disc}\dashv \Gamma$ can be thought of as "connected components.

For $\mathsf C$ the category of graphs and graph morphisms, $\pi_0$ takes a graph to the set of its connected components, where vertices lie in the same component if they are connected by a path.

For $\mathsf C$ the category of directed graphs, the same assertion holds.

Question. How to modify the adjunction above to obtain a "strongly connected components" functor? Vertices of a directed graph are strongly connected if there is a path between them in each direction.

Best Answer

The existence of such an adjoint triple in particular requires the strongly connected components functor to be a left adjoint. But in fact this fact is not a left adjoint, since it doesn't preserve colimits.

To see this, consider the span formed by the discrete graph on two vertices, included in the two two-vertex graphs which have one edge each (in opposite directions). Their pushout is the two-vertex graph with an edge in each direction, which is strongly connected. At the level of strongly connected components, you get the identity span between two-element sets, so their pushout still has two elements. Thus the pushout is not preserved.

Conclusion: There is no adjoint triple with the strongly connected components functor on the left.

There's some ambiguity about which category of directed graphs you actually have in mind, but the above argument works in all obvious candidates. If it doesn't work in yours, then you should be more explicit about what your category is.

Related Question