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

Topic: plane graphs in a PRO

Amar Hadzihasanovic (Jun 27 2021 at 11:48):

There is a (single-sorted) PRO with a single generator $g_{n,m}: n \to m$ for all $n, m \in \mathbb{N}$ and no equations.
(This can be characterised as the monoidal category whose delooping is the terminal 2-polygraph (or 2-computad) in the category of 2-polygraphs with functors that send generators to generators of the same dimension.)

Now, add a dual pair $\eta: 0 \to 2$, $\varepsilon: 2 \to 0$ and impose the triangle/zigzag/snake equations and that

$$(g_{n,m} \otimes \mathrm{id}_1) ; (\mathrm{id}_{m-1} \otimes \varepsilon) = (\mathrm{id}_1 \otimes g_{n,m}) ; (\varepsilon \otimes \mathrm{id}_{m-1}) = g_{n+1,m-1}, \quad (m >0),$$

$$(\mathrm{id}_{n-1} \otimes \eta) ; (g_{n,m} \otimes \mathrm{id}_1) = (\eta \otimes \mathrm{id}_{n-1}) ; (\mathrm{id}_1 \otimes g_{n,m}) = g_{n-1,m+1}, \quad (n > 0),$$

that is, make the $g_{n,m}$ closed under “turning an input into an output, and vice versa, using a duality”. Of course, this is still a PRO, in particular a rigid monoidal one.

Intuitively, I think the following should be true:

The “scalars” in this PRO, that is, the morphisms $0 \to 0$, correspond bijectively to plane graphs.

Does anyone know if/where this, or something equivalent (perhaps in some variant of operads), has been proved?

Amar Hadzihasanovic (Jun 27 2021 at 13:14):

(Correction: it should be plane graphs that can also contain copies of a 'vertex-less loop')

Jules Hedges (Jun 27 2021 at 18:35):

Somehow I had a feeling since a long time that something like this should be true but I never wrote down the details like this. So yeah, I definitely agree that this should be true, but pretty sure I never saw it anywhere

Jules Hedges (Jun 27 2021 at 18:38):

I'm not sure whether it's possible to simplify this into something involving Frobenius algebras

Jules Hedges (Jun 27 2021 at 18:40):

The pro generated by a special Frobenius algebra looks at least related to this, but not the same

Jules Hedges (Jun 27 2021 at 18:44):

The non-scalar morphisms of this are a bit weird, in particular they're not open graphs

Amar Hadzihasanovic (Jun 27 2021 at 18:48):

On Twitter, Robin Piedeleu mentioned that there is a similar result for generic (non-plane) graphs and the PROP of commutative special Frobenius algebras + a single generator $1 \to 1$ not subject to any axioms. He linked to a paper by Rosebrugh, Sabadini, and Walters but I still haven't decoded it.

Amar Hadzihasanovic (Jun 27 2021 at 18:49):

So he suggested that perhaps the PRO of “a special Frobenius algebra + a single generator $1 \to 1$” may similarly be a PRO of “open plane graphs”.

Amar Hadzihasanovic (Jun 27 2021 at 18:52):

Compared to my suggestion, this does have the advantage that the “vertex-less loop” is excluded; on the other hand, the equational theory is a bit more complicated so the passage diagrams -> graphs is a bit more indirect. (Essentially one should use the “spider presentation” of Frobenius algebras and reduce any diagram to the normal form where “all spiders that can merge have merged”.)

Jules Hedges (Jun 27 2021 at 18:54):

There's also this: https://www.sciencedirect.com/science/article/pii/S1571066115000766

John Baez (Jun 27 2021 at 19:21):

Amar Hadzihasanovic said:

There is a (single-sorted) PRO with a single generator $g_{n,m}: n \to m$ for all $n, m \in \mathbb{N}$ and no equations.
(This can be characterised as the monoidal category whose delooping is the terminal 2-polygraph (or 2-computad) in the category of 2-polygraphs with functors that send generators to generators of the same dimension.)

Now, add a dual pair $\eta: 0 \to 2$, $\varepsilon: 2 \to 0$ and impose the triangle/zigzag/snake equations and [...]
make the $g_{n,m}$ closed under “turning an input into an output, and vice versa, using a duality”. Of course, this is still a PRO, in particular a rigid monoidal one.

Intuitively, I think the following should be true:

The “scalars” in this PRO, that is, the morphisms $0 \to 0$, correspond bijectively to plane graphs.

Does anyone know if/where this, or something equivalent (perhaps in some variant of operads), has been proved?

I've never seen it written down, but I like this conjecture a lot. I bet it should be possible to prove this using known results on planar string diagrams, like those in Joyal and Streets The geometry of tensor calculus, I.

(The correction you added, involving the vertexless loop, makes it a bit less pretty - but more true. )

Jules Hedges (Jun 27 2021 at 19:29):

This is defining a pro, so can just add as an axiom that a closed loop equals empty space

Amar Hadzihasanovic (Jun 27 2021 at 19:41):

I hope @Joachim Kock will forgive me if I summon him -- I have a vague recollection of him discussing a formalism for graphs that also “accidentally” included the vertex-less loop, and his work here seems relevant.

John Baez (Jun 27 2021 at 19:44):

Yes, I was thinking about him just now. His formalism for is designed to allow edges with just a source and edge with just a target...

Joachim Kock (Jun 28 2021 at 08:10):

One place to look for a graph formalism like that could be the book of Hackney, Robertson and Yau. They have directed graphs with open-ended edges, allow edges to bend around, and even have special support for the loop without vertices. I don't recall having seen the precise theorem mentioned, though.

Joachim Kock (Jun 28 2021 at 08:12):

In my paper, linked by Amar, all graphs are progressive, like in Joyal-Street, and in particular there are no bent-around edges or loops. It can still be used to present the prop Amar asks for, as a category of sheaves on the progressive graphs (or equivalently, presheaves on elementary graphs), by adding the bending wires as special (0,2) and (2,0) nodes, as explained by Amar.

Joachim Kock (Jun 28 2021 at 08:15):

(The 'accident' with the loop with no vertices was an accident in the other direction: in the formalism for undirected graphs from my extended abstract with André Joyal, there was no such vertexless loop, and we thought it was not needed. But it later turned out the monad we used is actually not well defined without that special graph :-( Sophie Raynor, in her PhD thesis (Aberdeen 2017), provided a fix, and it is also possible to get around the problem by adding the loop by hand, as in Hackney-Robertson-Yau.)

Joachim Kock (Jun 28 2021 at 08:22):

Speaking of Frobenius algebras in this context, the Rosebrugh-Sabadini-Walters paper already mentioned shows that the prop for special commutative Frobenius algebras is given by the structured-cospan category of finite graphs (as usual, composed by pushout). This result has turned out to be really useful. Here is a variant of that result that I hope one day will find an application, but it is sort of cute anyway: if you upgrade from sets to groupoids (or homotopy 1-types) and use composition by homotopy pushout instead of ordinary pushout, then you get all commutative Frobenius algebras instead of only the special ones. This is a short 4-page paper with David Spivak, Homotopy composition of cospans, but here is a 1-line version: the reason is that the speciality condition throws away genus information, whereas with 1-types you can keep track of this data.

Joachim Kock (Jun 28 2021 at 08:34):

For an electrical circuit, the lack of speciality condition would mean that the electrons running in it would care about the topology of the copper wiring, rather than just whether there is a connection or not. This sounds a bit strange. But apparently Betti numbers of graphs were actually invented by Kirchhoff in electrical engineering long before Betti (I think John told me this), so it could be fun if there were some use of the non-special Frobenius prop...

Robin Piedeleu (Jun 28 2021 at 09:24):

I replied to @Amar Hadzihasanovic on twitter about this topic and thought I'd also give the same reference here.

There is a prop for open graphs (its morphisms are cospans of graphs with discrete legs so that its $0\rightarrow 0$ morphisms are the usual graphs). This prop can be given a presentation as the the prop of a special commutative Frobenius algebra with an additional $e: 1\to 1$ generator (satisfying no equations). This paper by Rosebrugh, Sabadini and Walters is the standard reference I believe.

The idea is that the Frobenius algebra (comultiplication, counit, multiplication, unit) interprets vertices and $e$ the edges of the graphs. This works because of the spider theorem: any connected network of the Frobenius algebra generators can be reduced to a normal form whose only relevant information are the number of dangling wires (this is like an open vertex with dangling half-eges if you want).

Of course this is all in the symmetric monoidal context. For the pro case, I believe the same idea would work but have not given it much thought.

Robin Piedeleu (Jun 28 2021 at 09:26):

Oops, sorry just noticed that @Amar Hadzihasanovic already explained the same idea above, based on my response on twitter. Oh well, a second explanation cannot hurt anyone!

Robin Piedeleu (Jun 28 2021 at 09:31):

Perhaps, what I can add is that you can impose all sorts of equations on this basic prop, in order to capture different flavours of graphs: you can eliminate parallel edges, vertex-loops, directedness, by making $e$ self-transpose, etc.

And, as I said on twitter, I also think of this prop as standing in relation to graphs as the category of tangles stands in relation to knots: functors out of it define graph invariants in the same way that functors out of the category of tangles define knot invariants. You just need to specify an object $X$ equipped with suitable Frobenius algebra in the target category and any endomorphism of $X$, in order to define a functorial graph invariant. Particular examples include colourings (so, the chromatic polynomial) and nowhere-zero flows.

Robin Piedeleu (Jun 28 2021 at 09:35):

For the chromatic polynomial I just dug this out of my notes. If the target category is enriched over $R$-modules and the scalar appearing below happens to be invertible, you can define a functor that captures the contraction-deletion property of the chromatic polynomial as follows:
$e =$
image.png

Amar Hadzihasanovic (Jun 28 2021 at 09:44):

Yes! I've basically been re-discovering some of this stuff on my own in the last few days; you must be way ahead of me. It doesn't seem to be a perspective much emphasised in the “graph invariant” literature (even though no doubt experts would find it obvious in retrospect :upside_down: ).

Robin Piedeleu (Jun 28 2021 at 09:44):

For $R = \mathbb{Q}$ and the generating object interpreted as $\mathbb{Q}^n$, we're counting $n$-colourings this way. I guess there's also a way to glue together all such functors by choosing the right $R$, to obtain the chromatic polynomial as a single functor.

Robin Piedeleu (Jun 28 2021 at 09:47):

Amar Hadzihasanovic said:

Yes! I've basically been re-discovering some of this stuff on my own in the last few days; you must be way ahead of me. It doesn't seem to be a perspective much emphasised in the “graph invariant” literature (even though no doubt experts would find it obvious in retrospect :upside_down: ).

Yes, I'm sure it would all feel quite obvious to experts. I've never seen the compositional perspective emphasised anywhere in the literature, though. I wonder if there is something interesting to gain by looking at all the standard algebraic invariants for open graphs. In the case of colourings, instead of a single number, we get a linear map that keeps track of how an open graph acts on colouring when composed with other open graphs.

Amar Hadzihasanovic (Jun 28 2021 at 09:49):

So for instance I've found a simple interpretation of graphs in the ZW calculus which satisfies the contraction-deletion recurrence (so it must be some valuation of the Tutte polynomial), but of course by completeness it can be computed “internally”, without sums. So I think it would be quite fun to try to do the same for more refined invariants.

Amar Hadzihasanovic (Jun 28 2021 at 09:51):

(I still have to figure out what this ZW invariant is computing.)

Amar Hadzihasanovic (Jun 28 2021 at 09:56):

Robin Piedeleu said:

Yes, I'm sure it would all feel quite obvious to experts. I've never seen the compositional perspective emphasised anywhere in the literature, though.

Yes, I find this quite surprising -- like, basically everywhere now the Jones polynomial is defined using the Kauffman bracket which is a monoidal functor into an $R\mathrm{Mod}$-enriched monoidal category (but let's not say it out loud); and everywhere it is said that the Jones polynomial is a special valuation of a polynomial for signed graphs; but for some reason nobody makes the obvious next step “define graph invariants with a bracket”?

Amar Hadzihasanovic (Jun 28 2021 at 09:59):

It's probably a case of braid diagrams & Reidemeister moves having been fully internalised by the knot community, but string diagrams & Frobenius equations not having the same status in the graph community?

Robin Piedeleu (Jun 28 2021 at 10:26):

Amar Hadzihasanovic said:

So for instance I've found a simple interpretation of graphs in the ZW calculus which satisfies the contraction-deletion recurrence (so it must be some valuation of the Tutte polynomial), but of course by completeness it can be computed “internally”, without sums. So I think it would be quite fun to try to do the same for more refined invariants.

Sounds great! I wondered if there was a way to axiomatise directly some of these invariants, but never got very far. I'd love to see what this looks like in ZX/ZW.

Robin Piedeleu (Jun 28 2021 at 13:20):

Robin Piedeleu said:

Of course this is all in the symmetric monoidal context. For the pro case, I believe the same idea would work but have not given it much thought.

One mismatch in the pro case is that two diagrams that represent the same planar graph might not be equal as diagrams. The isomorphism between the two concrete representation might require symmetry when implemented via equational reasoning. For example,
image.png and image.png

Robin Piedeleu (Jun 28 2021 at 13:22):

I guess it depends what notion of isomorphism you're after. But this pro will force one on you.

Robin Piedeleu (Jun 28 2021 at 13:25):

(By "this pro", I meant the one you get by taking the prop we've been discussing and dropping axioms involving the symmetry).

Amar Hadzihasanovic (Jun 28 2021 at 13:53):

Ah, but that's why I was making the distinction between planar and plane; I'd expect this PRO to encode a specific embedding of a graph. (I think that's equivalent to a tiling of the 2-sphere together with a chosen 'outer' face? Maybe that's another perspective.)

Robin Piedeleu (Jun 28 2021 at 13:55):

Ah right, I missed that! Then it seems fine.