4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ @TobiasFritz: That seems to me like it should be an answer! While there’s a little ambiguity about what “category of directed graphs” the OP has in mind, your example works in all such categories I can think of. $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented May 29, 2022 at 17:51
  • $\begingroup$ Right, I've turned my comment into an answer. $\endgroup$
    – Tobias Fritz
    Commented May 29, 2022 at 18:33
  • 1
    $\begingroup$ A natural analogue of the adjunction Graphs to Sets, seems to be Directed graphs to Posets. In one direction a directed graph gets taken to its set of connected components, with partial order given by whether not there is a path from one component to the other. In the other direction a poset is given the structure of a directed graph by placing an edge $\vec{xy}$ whenever $x>y$. Here a morphism of directed graphs is a map $f$ on the underlying sets of vertices, satisfying that if there is an edge $x$ to $y$, then either $f(x)=f(y)$ or there is an edge $f(x)$ to $f(y)$. $\endgroup$
    – tkf
    Commented May 30, 2022 at 11:50
  • 1
    $\begingroup$ @tkf it seems changing the base to posets gives strongly connected components, so this is exactly what I was looking for! Should have thought about it :) $\endgroup$
    – Arrow
    Commented Jun 2, 2022 at 9:59

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Do you see any way of defining strongly connected components using the connected components functor and some other "canonical" constructions? $\endgroup$
    – Arrow
    Commented May 29, 2022 at 20:32
  • 1
    $\begingroup$ @TobiasFritz Really? For $G$ an oriented triangle (edges $1\to 2$, $2\to 3$ and $3\to 1$), $G\cap G^{op}$ is the graph with $3$ vertices and no edges, but $G$ has a single strongly connected component. Am I missing something? $\endgroup$
    – Aurel
    Commented May 30, 2022 at 8:13
  • $\begingroup$ @Aurel, of course, sorry, I'll delete my comment. Then I don't know. $\endgroup$
    – Tobias Fritz
    Commented May 30, 2022 at 9:25

You must log in to answer this question.

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