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: theory: applied category theory

Topic: Parallel diagram rewriting

Amar Hadzihasanovic (Dec 08 2020 at 13:44):

I have written a twitter thread on a fact that I believe is little-known, and may be of interest to whoever studies string or wiring diagrams (or higher categories).

I have some equations of string diagrams. I can apply two equations to two *disjoint* subdiagrams of a larger string diagram. Can I apply both of them at the same time? The answer is *yes* in 1d and 2d. Counterintuitively, it is *no* in 3d or higher. A thread: 1/12

- Amar Hadzihasanovic (@amar_hh)

It's about the following problem: if we can apply some equations/rewrites to disjoint subdiagrams of a string diagram, can we apply them simultaneously?
The answer turns out to depend on the dimension in which the diagrams “live”.
This may have an impact on the problem of parallelising automated diagram rewriting or equation solving.

Antonin Delpeuch (Dec 08 2020 at 13:53):

Very interesting! This sounds like something that deserves better than a Twitter thread! Especially because when I click the link, I get "This is not available to you". I would encourage as many as possible to follow @John Baez's example (https://twitter.com/johncarlosbaez) and write up their thoughts elsewhere :)

Amar Hadzihasanovic (Dec 08 2020 at 14:03):

@Antonin Delpeuch Oh no, really? I was convinced that posts on twitter were visible to the public including non-users, unless set otherwise?

Reid Barton (Dec 08 2020 at 14:07):

There's some issue with following links to twitter if you have some privacy options set in Firefox

Reid Barton (Dec 08 2020 at 14:07):

If you shift-reload the twitter.com page, it should work

Nathanael Arkor (Dec 08 2020 at 14:12):

Is this essentially for the same reason that the interchange law holds up to equality in bicategories, but only up to a (higher) equivalence in higher categories (for n > 2)?

Amar Hadzihasanovic (Dec 08 2020 at 14:16):

I am happy to say that no, it's not! (I'm happy because usually everything that's different for tricategories compared to bicategories is due to that).
You can have diagrams interpreted in strict 3-categories (where interchange holds up to equality) with the same obstruction. Power's original counterexample is like that.

Nathanael Arkor (Dec 08 2020 at 14:17):

Ah, interesting.

Morgan Rogers (he/him) (Dec 08 2020 at 14:29):

I don't understand why, in the example you give, after applying Frobenius to one or other of the subdiagrams, the other "stops being a subdiagram". What definition of subdiagram are you using that makes this the case?

Morgan Rogers (he/him) (Dec 08 2020 at 14:30):

In other words, why can't I do this:
Frobenius-mess.png

Reid Barton (Dec 08 2020 at 14:34):

I think the problem is you would need to create a cup/cap in the process

Amar Hadzihasanovic (Dec 08 2020 at 14:37):

Because in general you can't “bend wires”. You can if you have dualisable cells, and then (via cobordism hypothesis) you are “rewriting manifolds” or something that's at least more manifold-like :)

A formal definition of subdiagram would be “something that can appear as a factor in an expression for the diagram as a composite of its individual cells” (I'm thinking here with “globular” n-categorical composition, but it should be possible to adapt to other algebras or combinatorics.)

Amar Hadzihasanovic (Dec 08 2020 at 14:40):

Or also, more informally, “whatever, substituted with any other diagram with the same boundary, yields another well-formed diagram”, and also “whatever, substituted with a single cell with the same boundary, yields another well-formed diagram”.

Morgan Rogers (he/him) (Dec 08 2020 at 15:00):

So you need the top and bottom endpoints of the subdiagram to be parallel (or parallel up to a deformation that doesn't involve bending wires back on themselves)? Hmm no, that still can't be quite right...

Morgan Rogers (he/him) (Dec 08 2020 at 15:02):

... like, this also isn't allowed, right? a-deformation.png

Amar Hadzihasanovic (Dec 08 2020 at 15:11):

Yeah, you can't have critical points, nor change which wires come “from the top” or “from the bottom” into a node.
But the intuition that “given a subdiagram, you can deform the diagram so that its endpoints are parallel, and all other nodes are either above or below” is correct.

John Baez (Dec 09 2020 at 01:39):

I don't know what game you're playing, but the equation Morgan marked with

$\stackrel{?}{=}$

is true for Frobenius algebras, or Frobenius monoids in any monoidal category.

John Baez (Dec 09 2020 at 01:41):

(I'm probably missing the point of the conversation, which was hard for me to follow.)

Amar Hadzihasanovic (Dec 09 2020 at 10:34):

In that particular point, we were discussing what kinds of deformations were allowed for all string diagrams, so nothing about Frobenius algebras specifically.

John Baez said:

(I'm probably missing the point of the conversation, which was hard for me to follow.)

I'm sorry that you didn't get much from this, I suppose I wrote it with people who are specifically interested in diagram rewriting in mind. Maybe I can try to tell it in this way, which is more algebraic.
This is a fact about $n$-categories for $n \geq 3$. Namely, $n = 3$ is the lowest dimension in which the following can happen:
There are $n$-cells $x, a, b$ in a freely generated (in the sense of polygraphs/computads) $n$-category such that

• $a$ appears as a factor in a factorisation of $x$,
• $b$ appears as a factor in another factorisation of $x$,
• $a$ and $b$ “only overlap in the boundary”, that is, any common factor of $a$ and $b$ is a factor of the source or target of $a$ and $b$, but
• there is no factorisation of $x$ that contains both $a$ and $b$ as factors.

Amar Hadzihasanovic (Dec 09 2020 at 10:42):

I find this interesting because unlike other things that similarly break down after the first few dimensions, like the ones that follow from Eckmann-Hilton, this one is “purely higher-categorical” in the sense that this situation can never happen in higher groupoids.

John Baez (Dec 09 2020 at 19:48):

Thanks, that's interesting. I don't know if it's connected to this, but it reminds me of this: in a monoidal bicategory it's no longer true that

$(1 \otimes f) \circ (g \otimes 1) = (g \otimes 1)\circ (1 \otimes f)$

for 1-morphisms $f: X \to X'$, $g : Y \to Y'$, since the two sides are just isomorphic in general. In string diagrams it means that the process of "pushing $g$ up and pulling $f$ down" can be a nontrivial 2-isomorphism.

Robin Piedeleu (Dec 10 2020 at 11:04):

Amar Hadzihasanovic said:

This is a fact about $n$-categories for $n \geq 3$. Namely, $n = 3$ is the lowest dimension in which the following can happen:
There are $n$-cells $x, a, b$ in a freely generated (in the sense of polygraphs/computads) $n$-category such that

• $a$ appears as a factor in a factorisation of $x$,
• $b$ appears as a factor in another factorisation of $x$,
• $a$ and $b$ “only overlap in the boundary”, that is, any common factor of $a$ and $b$ is a factor of the source or target of $a$ and $b$, but
• there is no factorisation of $x$ that contains both $a$ and $b$ as factors.

Just to be clear, what you call "factor" in this algebraic reformulation, corresponds to the subdiagrams of your rewriting (counter-)example on twitter, right? For instance, $a$ and $b$ here would be the subdiagrams highlighted in blue and pink, and $x$ the larger diagram.

Amar Hadzihasanovic (Dec 10 2020 at 11:29):

@Robin Piedeleu Yes.

Amar Hadzihasanovic (Dec 10 2020 at 11:58):

@John Baez It's not directly connected to the fact you mention (because what I describe also applies to a strict monoidal 2-category, where those two are equal on-the-nose). But it does imply something which has to do with interchange equations like the one you wrote.

That is, you could think of generalising that equation in this way: say that

$$w_1(f) \circ w_2(g) = w'_2(g) \circ w'_1(f)$$

whenever $w_i(-), w'_i(-)$ are some “whiskered contexts” -- that is, say $w_1(f)$ is “f whiskered with some lower-dimensional cells” -- such that the “holes” for $f$ and $g$ may only overlap on their boundary (and all types match; for example $w'_2(-)$ would have to be $w_2(-)$ with the target of $f$ replacing the source of $f$).

In your equation, you would have for example $w_1(-) = 1 \otimes -$ and $w_2(-) = - \otimes 1$, with whatever the right types are.

Then the fact that I mentioned implies that such a “generalised interchange equation” holds for 2-categories and 3-categories, but fails for 4-categories or higher! You can have situations in which only one side of the equation is well-formed.

Amar Hadzihasanovic (Dec 10 2020 at 11:59):

(So not only there cannot be an equation between the two sides, but neither there can be an isomorphism).