Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: practice: terminology & notation

Topic: Name for this kind of graph homomorphism?

Mike Stay (Apr 04 2024 at 17:41):

Let $G[v]$ be the subgraph of the directed graph $G$ reachable from the vertex $v$. What do you call a graph homomorphism $f:G \to H$ where
$G[v_1] \cong G[v_2] \Rightarrow H[f(v_1)] \cong H[f(v_2)]$?
"Subgraph-isomorphism-preserving" is a bit of a mouthful.

Matteo Capucci (he/him) (Apr 05 2024 at 07:02):

Is this some kind of locality property?

Mike Stay (Apr 08 2024 at 15:17):

The graphs I'm interested in have structural-equivalence-classes of terms of a process calculus as vertices and context-labeled transitions as directed edges. Induced subgraph isomorphism is essentially bisimilarity. Graph homomorphisms that preserve bisimilarity are a useful notion of morphism from one language into another that is semantic rather than syntactic. Compilation is an epi, abstract interpretation is a mono.

Chris Grossack (they/them) (Apr 08 2024 at 15:41):

Is there a reason to not call it "bisimilarity-preserving"? If $v_1$ and $v_2$ are bisimilar in $G$, then $f v_1$ and $f v_2$ should be bisimilar in $H$.

Mike Stay (Apr 08 2024 at 16:39):

That's fair. I just wondered if there was a pre-existing name for it.

Eric M Downes (May 23 2024 at 12:46):

It sounds like the map on subgraphs is the left adjoint of a localic morphism in the [[specialization topology]] (aka Alexandrov topology; upper sets are open); "bisimilarity-preserving" sure is hard to beat but maybe check with the Stone-spaces folks, seems intimately related.