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: learning: questions

Topic: enriched graphs

Paolo Perrone (Feb 18 2022 at 10:02):

Just as enriched categories, one can talk about "enriched graphs", and the notion appears in the literature here and there.
Has anyone studied them or worked with them consistently? (Maybe some graph theorists?)

John Baez (Feb 18 2022 at 17:45):

I've definitely seen stuff about $V$-graphs for a category $V$: they've got a set of vertices and for any pair of vertices $x,y$ an object $E(x,y) \in V$.

John Baez (Feb 18 2022 at 17:46):

But I don't know a paper all about them.

Matteo Capucci (he/him) (Feb 18 2022 at 17:56):

@Jade Master's thesis perhaps?

Mike Shulman (Feb 18 2022 at 18:01):

Graph theorists certainly study graphs with "weights" on the edges, which you could call $\mathbb{R}$-enriched...

John Baez (Feb 18 2022 at 18:54):

In her thesis Jade considers graphs with edges labelled by elements of a quantale she calls $R$. This is a nice special case of $V$-graphs, and it includes the weighted graphs Mike just mentioned.

Paolo Perrone (Feb 18 2022 at 19:30):

Mike Shulman said:

Graph theorists certainly study graphs with "weights" on the edges, which you could call $\mathbb{R}$-enriched...

What are their morphisms? Or at least, which maps between them are relevant for the purpose of graph theorists?

Mike Shulman (Feb 18 2022 at 19:41):

I don't know.

John Baez (Feb 18 2022 at 20:25):

Graph theorists don't think about morphisms as much as you'd hope. I guess a category theorist who never composes morphisms is called a graph theorist. :upside_down:

Morgan Rogers (he/him) (Feb 18 2022 at 20:47):

I'm pretty sure there's a whole conference dedicated to graph transformations, so that can't be true...

David Egolf (Feb 18 2022 at 21:36):

Perhaps relevant here, apparently one can "colour" edges in a graph. In this case, you have a graph with vertices $V$ and edges $E$ and a function $c: E \to S$ where $S$ is presumably a set of colours.

Jade Master (Feb 18 2022 at 21:37):

@Paolo Perrone I have written about enriched graphs in my thesis. Mostly I was concerned with the free enriched category construction (on an enriched graph) and the compositionality of this construction in the case of quantale-enrichment like John said. There is also a paper by Wolff on the free enriched category construction: https://www.sciencedirect.com/science/article/pii/0022404974900188

As for the morphisms there are two choices I've thought about. In both, you have a function $f: X \to Y$ between sets of vertices. Then you can choose the "pullback option" which is a V-morphism $hom(x,y) \to hom(f(x),f(y))$ for all x and y in X. The other option is the "pushforward option" which is a V-morphism $\sum_{x,y \in f^{-1}(x'),f^{-1}(y')} hom(x,y) \to hom(x',y')$ for all x' and y' in Y.

Jade Master (Feb 18 2022 at 21:40):

In my thesis it turned out that I needed the pushforward option but there are definitely situations where you would want the pullback morphisms... I'm pretty sure that's what Wolff uses.

Jade Master (Feb 18 2022 at 21:43):

Also yes it's true, when enriching in a quantale enriched categories are weighted graphs (directed, self edges allowed, no multiple edges) and the free enriched category solves the algebraic path problem...which is a generalization of the shortest path problem to wide range of contexts.

Jade Master (Feb 18 2022 at 21:49):

I'm calling it pullback because you're "pulling back" the V-category on Y along f (not to be confused with the categorical pullback) and "pushforward" because you're pushing forward the V-category on X along f.

Jade Master (Feb 18 2022 at 21:55):

I think for both choices of morphism you have all finite colimits...there are also probably other nice properties of these categories. Does that help? Is there anything else specific you would like to know about them?

David Egolf (Feb 18 2022 at 21:58):

I don't know if this has any relation to what people actually do - which appears to be well over my head. But, I seem to recall that you can make a graph using a functor $G: C \to Set$ where $C$ is this category:
category C

Then $G(1)$ is the set of edges, $G(2)$ is the set of vertices, $G(a)$ sends each edge to its source vertex and $G(b)$ sends each edge to its target vertex.

Maybe one can get a coloured graph by consider a functor $F: C' \to Set$, where $C'$ is this category:
category C'

Here, $C'(3)$ is a set of colours and $C'(c)$ is a function that sends each edge to its colour.

Then one could consider natural transformations between these functors, which would give some notion of morphism between coloured graphs.

Jade Master (Feb 18 2022 at 22:00):

Sure that's a perfectly cromulent definition, they're not the thing which generates enriched categories however...if that's what you're working for.

Mike Shulman (Feb 18 2022 at 22:11):

I must be missing something; aren't the pullback and pushforward definitions of morphism equivalent?

Jade Master (Feb 18 2022 at 22:22):

@Mike Shulman I don't see why they would be equivalent. For one thing you have a different number of V-morphisms when X and Y are different sizes. One for each pair in X for the pullback and one for each pair in Y for the pushforward.

Jade Master (Feb 18 2022 at 22:25):

Oh wait I think I see what you mean...the universal property of coproducts means the pushforward is a V-morphism from hom(x,y) -> hom(x',y') for each x and y in the preimage of x',y' and for each x',y' in Y... but is that the same as a V-morphism hom(x,y) -> hom(f(x),f(y)) for each x, and y in X?

Jade Master (Feb 18 2022 at 22:27):

I think they are the same when f is injective.

Jade Master (Feb 18 2022 at 22:41):

Oh wait maybe they are the same...

Mike Shulman (Feb 18 2022 at 22:55):

"a morphism hom(x,y) -> hom(x',y') for each x' and y', and each x and y in the preimages of x' and y' respectively" means "...for each x, y, x', y' such that f(x) = x' and f(y) = y'", which is the same as "a morphism hom(x,y) -> hom(f(x),f(y)) for each x and y".

Jade Master (Feb 19 2022 at 08:17):

Yes you're right they are the same. That's a nice observation and now that I think about it, it would be a bit concerning if they weren't the same because they both give enriched functors between their free categories.

Paolo Perrone (Feb 19 2022 at 09:44):

Thank you Jade! That seems very interesting.

Paolo Perrone (Feb 19 2022 at 09:45):

(I have to read your thesis.)

Fabrizio Genovese (Feb 22 2022 at 20:59):

Morgan Rogers (he/him) said:

I'm pretty sure there's a whole conference dedicated to graph transformations, so that can't be true...

Yes, it's called ICGT. In that context, many usually employ the "classic" definition of graph transformation and try to generalize it in a way that plays well with the enrichment. I must stress that the focus is very different tho: most often one cares about graph rewriting that is done via single, double, sesqui-pushout and similar techniques. So in the end your definition of morphism is good as long as you have an adhesive category.

John Baez (Feb 22 2022 at 21:04):

What I meant, btw, is that if you read an introductory text on graph theory, they will often define graphs but not morphisms of graphs. Which compared to a ring theory or group theory course is very weird!

Fabrizio Genovese (Feb 22 2022 at 21:05):

As long as they don't cover graph transformations I do agree. They may focus on stuff like hamiltonian/eulerian paths, centrality measures etc. But graph rewriting is a pretty big topic in computer science, I doubt there are modern books on graph theory that don't mention graph rewriting, if only tangentially

Fabrizio Genovese (Feb 22 2022 at 21:06):

(Or at least I hope so, lol)

John Baez (Feb 22 2022 at 21:06):

I don't know!

John Baez (Feb 22 2022 at 21:07):

I bet you might be surprised!

John Baez (Feb 22 2022 at 21:08):

I'm imagining group theory where the basic textbooks don't mention homomorphisms but there are certain conference series that focus on homomorphisms. :upside_down:

John Baez (Feb 22 2022 at 21:09):

(Of course "graph transformations" are more fancy than the basic "graph morphisms".)

Martti Karvonen (Feb 22 2022 at 21:43):

Idk what the standard for "modern" is, but I don't think Diestel's book says anything about rewriting, and I'm not sure if the book talks about morphisms of graphs either. Of course, it's a pure math book and not a TCS book, so maybe the situation is different with books written for/by computer scientists.

Fabrizio Genovese (Feb 22 2022 at 22:50):

John Baez said:

I'm imagining group theory where the basic textbooks don't mention homomorphisms but there are certain conference series that focus on homomorphisms. :upside_down:

I wouldn't even know how to state isomorphism theorems (or to define an isomorphism of groups, actually) without introducing homomorphisms...

Reid Barton (Feb 22 2022 at 23:45):

Funny you say that, because in some random MIT course notes (from the CS department) that I found by searching for "graph theory", they define isomorphism of graphs but not any sort of morphisms of graphs (aside from subgraphs).

Reid Barton (Feb 22 2022 at 23:46):

(I know you said groups not graphs, though.)

John Baez (Feb 22 2022 at 23:58):

I was actually going to say that isomorphisms of gadgets are usually easier to define than morphisms.

For example: in morphisms of monoids you get to decide whether the identity is being treated as structure - which must be preserved - or mere property, which needn't. For isomorphisms, these two choices work out to be the same.

Similar issues show up in the various kinds of graphs, I think.

Fawzi Hreiki (Feb 23 2022 at 00:00):

Reid Barton said:

Funny you say that, because in some random MIT course notes (from the CS department) that I found by searching for "graph theory", they define isomorphism of graphs but not any sort of morphisms of graphs (aside from subgraphs).

This is unfortunately the case with most graph theory and combinatorics texts.

John Baez (Feb 23 2022 at 00:01):

They're trapped in the pre-categorical era.

John Baez (Feb 23 2022 at 00:02):

They cannot talk about any invariant of graphs being functorial (except w.r.t. isomorphisms).

Fawzi Hreiki (Feb 23 2022 at 00:02):

It's particularly frustrating since many combinatorial structures (trees, graphs, etc..) assemble into presheaf categories which means that there is a lot of extra machinery around that can be used.

Zhen Lin Low (Feb 23 2022 at 00:06):

Look, I'm sure it's fun to be smug and grouse about those "other" mathematicians who are "trapped in the pre-categorical era" but I hope you realise how this just makes them even less receptive to your ideas?

John Baez (Feb 23 2022 at 00:06):

I seem to be doing fine in getting people to pay attention to my ideas.

Zhen Lin Low (Feb 23 2022 at 00:07):

Lucky you.

John Baez (Feb 23 2022 at 00:08):

Not luck. Shitloads of hard work.

John Baez (Feb 23 2022 at 00:09):

I spend hours each day explaining math to people. And I don't run around the halls of my department, stopping graph theorists and telling them "you're trapped in the pre-categorical era". :upside_down:

Zhen Lin Low (Feb 23 2022 at 00:10):

Good! Then why do you do it here, in a public forum, on the internet, where your words are likely to found by a search engine and used against you forever?

John Baez (Feb 23 2022 at 00:13):

I'm really not worried that graph theorists are going to read that remark and "use it against me" (how, exactly?) or get so upset they vow to never use categories.

Zhen Lin Low (Feb 23 2022 at 00:14):

Lucky you.

John Baez (Feb 23 2022 at 00:14):

Well, if I'm really so "lucky" I might as well take advantage of it.

Zhen Lin Low (Feb 23 2022 at 00:15):

To put it in more modern lingo: check your privilege, man.

John Baez (Feb 23 2022 at 00:18):

If some people here have graph theorist colleagues who may not give them tenure because they read the archives of this conversation, then yes they should be careful about what they say. Maybe they even should attack me for what I just said!

John Baez (Feb 23 2022 at 00:19):

Then they can say "yeah, Baez said some nasty things about graph theorists, but I defended you".

John Baez (Feb 23 2022 at 00:23):

But as a "privileged" old fogey, I feel I should say what I think.

John Baez (Feb 23 2022 at 00:23):

I have nothing against graph theorists or graph theory, by the way! I just think they could explore lots of new questions if they chose some categories of graphs and used them to study functorial invariants of graphs, the way people do in topology, group theory, etc.

Morgan Rogers (he/him) (Feb 23 2022 at 06:47):

I second John's final comment, but I also expect that there are people doing exactly that somewhere, just not enough of them to make it mainstream.

John Baez (Feb 23 2022 at 06:58):

They may need to crack some well-known open problems, or invent great new ones, before these techniques catch on. (That's how it worked in topology.)

Paolo Perrone (Feb 23 2022 at 10:11):

What are graph transformations?

Jade Master (Feb 23 2022 at 10:35):

Paolo Perrone said:

What are graph transformations?

Not an expert...but my understanding is that graph transformations are about formulating "rewrite rules" for graphs and studying the properties or using the resulting "rewrite systems". You might have a rule for example that whenever you "find" a graph G inside a graph H you "replace" G with H. Then you may chain these replacements together in increasingly complicated ways. Deciding what exactly you mean by "find" and "replace" requires a certain amount of care, and I think the most common approach is to use double pushout rewriting. I could tell you a bit about that sometime if you like.

Leopold Schlicht (Feb 23 2022 at 12:13):

Fawzi Hreiki said:

Reid Barton said:

Funny you say that, because in some random MIT course notes (from the CS department) that I found by searching for "graph theory", they define isomorphism of graphs but not any sort of morphisms of graphs (aside from subgraphs).

This is unfortunately the case with most graph theory and combinatorics texts.

John Baez said:

They're trapped in the pre-categorical era.

Fawzi Hreiki said:

It's particularly frustrating since many combinatorial structures (trees, graphs, etc..) assemble into presheaf categories which means that there is a lot of extra machinery around that can be used.

That sounds like you are talking graph theorists down. Could you give me one concrete application of introducing categorical terminology in graph theory? For instance, I don't think it's particularly useful for graph theorists to observe that the category of directed multigraphs has a subobject classifier, or what does "extra machinery" of presheaf categories refer to?

Leopold Schlicht (Feb 23 2022 at 12:14):

Also, what's wrong with only defining isomorphisms (and not homomorphisms)? I thought groupoids are nice categorical objects too.

Jade Master (Feb 23 2022 at 12:17):

I could give you an example, double pushout graph rewriting :P

Leopold Schlicht (Feb 23 2022 at 12:19):

Did that solve problems graph theorists came up with before?

Jade Master (Feb 23 2022 at 12:20):

I think it's more useful in the sciences...for example modeling the unfolding of proteins or sequences of chemical reactions.

Jade Master (Feb 23 2022 at 12:22):

@ww knows a lot about this :) much more than me. I'd love to hear his perspective.

Leopold Schlicht (Feb 23 2022 at 15:24):

Reid Barton said:

Funny you say that, because in some random MIT course notes (from the CS department) that I found by searching for "graph theory", they define isomorphism of graphs but not any sort of morphisms of graphs (aside from subgraphs).

It's funny that even Jacob Lurie talks almost never about morphisms in his notes on combinatorics. But he talks about isomorphisms a lot. See for instance Lecture 14: there he defines isomorphisms between "species" (Definition 2), but not morphisms.

Fawzi Hreiki (Feb 23 2022 at 15:38):

Leopold Schlicht said:

Fawzi Hreiki said:

Reid Barton said:

Funny you say that, because in some random MIT course notes (from the CS department) that I found by searching for "graph theory", they define isomorphism of graphs but not any sort of morphisms of graphs (aside from subgraphs).

This is unfortunately the case with most graph theory and combinatorics texts.

John Baez said:

They're trapped in the pre-categorical era.

Fawzi Hreiki said:

It's particularly frustrating since many combinatorial structures (trees, graphs, etc..) assemble into presheaf categories which means that there is a lot of extra machinery around that can be used.

That sounds like you are talking graph theorists down. Could you give me one concrete application of introducing categorical terminology in graph theory? For instance, I don't think it's particularly useful for graph theorists to observe that the category of directed multigraphs has a subobject classifier, or what does "extra machinery" of presheaf categories refer to?

I'm definitely not talking graph theorists down at all. It's just an objective statement about what you'll find (or rather, not find) in most of the primary sources. If you want a graph theory book that actually does deal with homomorphisms, there is "Graphs and Homomorphisms" by Hell & Nešetřil.

Leopold Schlicht (Feb 23 2022 at 15:39):

I know that book.

Leopold Schlicht (Feb 23 2022 at 15:44):

Having studied texts on graph homomorpisms myself, I don't think invoking category-theoretic terminology will help much proving the conjectures graph theorists are interested in.

Leopold Schlicht (Feb 23 2022 at 15:49):

At least until somebody shows how. :-) But I think it's not appropriate to talk graph theorists down who are not using category theory. If category theorists think graph theorists should use category theory, I think it's their task to give concrete suggestions how category theory could be useful.

Leopold Schlicht (Feb 23 2022 at 15:53):

Maybe category theory suggests new questions. But why "should" graph theorists be interested in them?

David Egolf (Feb 23 2022 at 16:00):

Leopold Schlicht said:

Also, what's wrong with only defining isomorphisms (and not homomorphisms)? I thought groupoids are nice categorical objects too.

I'd be interested in answers to this question.
To take an initial stab at why we'd want morphisms that aren't isomorphisms: To my (a category theory beginner) understanding, we want non-isomorphic morphisms to enable us to compare objects that are related, yet significantly distinct. If we want to be able to talk about combining objects (e.g. through products), or looking at subobjects, I would expect we would want a category with morphsims that are not isomorphisms.

David Egolf (Feb 23 2022 at 16:02):

I suppose another angle to try and answer this question would be to take a category, like $Set$ for example, and see what happens to limits and colimits if we delete all morphisms that are not isomorphisms.

Leopold Schlicht (Feb 23 2022 at 16:06):

David Egolf said:

If we want to be able to talk about combining objects (e.g. through products), or looking at subobjects, I would expect we would want a category with morphsims that are not isomorphisms.

I agree. But I don't think graph theorists should talk about categorical products or subobjects. They'll define the notions of products of graphs and subgraphs they need anyway, without having to know any category theory.

Morgan Rogers (he/him) (Feb 23 2022 at 16:07):

Leopold Schlicht said:

If category theorists think graph theorists should use category theory, I think it's their task to give concrete suggestions how category theory could be useful.

I passionately agree with this. No change in perspective is self-justifying, and no sceptic will be convinced of the value of categories or toposes just because we tell them they're missing out without having evidence to back that claim up. The burden of proof is on us, a priori.

That said, I still find the position of bitter sceptic of category theory bemusing. Even lacking final evidence that using categories will be productive, its tools are pervasive, and their success is hard to deny. While you can avoid categorical reasoning and it can often be excised from a proof if you insist on it, that doesn't detract from the pathways to results that it creates. And as I gain experience in category theory, I can increasingly figure out potential lines of attack using categorical tools once I'm exposed to a problem.

Morgan Rogers (he/him) (Feb 23 2022 at 16:09):

Leopold Schlicht said:

David Egolf said:

If we want to be able to talk about combining objects (e.g. through products), or looking at subobjects, I would expect we would want a category with morphsims that are not isomorphisms.

I agree. But I don't think graph theorists should talk about categorical products or subobjects. They'll define the notions of products of graphs and subgraphs they need anyway, without having to know any category theory.

You can talk about the collection of automorphisms of a graph without acknowledging that it's a group, too. But recognizing structure clearly puts tools at your disposal that you don't have when you ignore that structure.

Joe Moeller (Feb 23 2022 at 16:12):

I'm just going to drop the name Tien Chih as someone who talking about graphs with categories.

Leopold Schlicht (Feb 23 2022 at 16:15):

What would be three specific such "tools"?

Paolo Perrone (Feb 23 2022 at 16:26):

Just to stir the pot. In this video it is explained what is meant by "limit of graphs".
https://youtu.be/7Gj9BH4IZ-4?t=200
(Don't stop at the beginning with graphons, but rather look at what they say starting from time 3:20.)
As I think was suggested by @fosco, it seems that colimits could be used in this setting. (I don't know if they would actually help with the problems in that field though, it's not my field.)

John Baez (Feb 23 2022 at 18:08):

Morgan Rogers (he/him) said:

Leopold Schlicht said:

If category theorists think graph theorists should use category theory, I think it's their task to give concrete suggestions how category theory could be useful.

I passionately agree with this. No change in perspective is self-justifying, and no sceptic will be convinced of the value of categories or toposes just because we tell them they're missing out without having evidence to back that claim up. The burden of proof is on us, a priori.

Yeah. You'll notice my complaint about graph theorists was spoken to "us". I really meant it when I said I don't go around telling graph theorists "You're trapped in the pre-categorical era!" That, or anything resemblng that, is almost useless.

If "we" get sufficiently upset that graph theorists don't make adequate use of morphisms of graphs, functors from a category of graphs to other graphs, and other standard mathematical techniques, maybe one of "us" will get motivated to do something interesting using these techniques.

I've spent the last 10 years trying to introduce category theory in chemistry, electrical circuit theory, control theory, Markov process theory, and now epidemiology - not by scolding people who work on those subjects, but by writing papers about these subjects.

If I had the energy I might try this in graph theory. But I don't! The first step might be to spend a few years learning more graph theory.

Morgan Rogers (he/him) (Feb 23 2022 at 18:24):

What would be three specific such "tools"?

I could just list categorical gadgets like limits and colimits, but presumably you were looking for more than that. Consider functors, adjunctions and monadicity. The first allows us to directly compare your category of graphs with another category, the second provides useful constraints on such a comparison, and the third guarantees and provides a construction of certain structures (including but not limited to limits and colimits) in your chosen category of graphs.

And all of those tools are just from an introductory text on category theory...

Of course, none of this is a guarantee of progress on what a graph theorist cares about. But it should be enough to convince you that category theory might be able to produce progress if enough work is put into it.

John Baez (Feb 23 2022 at 18:25):

Paolo Perrone said:

What are graph transformations?

If you want a category theorist's answer to this question, try this:

• Daniel Cicala, Rewriting Structured Cospans: A Syntax For Open Systems.

He explains double pushout graph rewriting (which is one answer to your question) and then generalizes the heck out of it, both by replacing the category of graphs with any topos, and by replacing objects (like graphs) with 'open' objects (like open graphs).

Graham Manuell (Feb 23 2022 at 18:41):

I actually share some of the skepticism of exactly how useful graph theorists would find category theory. That said, there is at least one prominent example I can think of where it was arguably useful. Hedetniemi's conjecture was an open problem in graph theory for over 50 years before it was disproved in 2019. The counterexample uses the exponential object in the category of graphs.

Leopold Schlicht (Feb 23 2022 at 18:42):

Morgan Rogers (he/him) said:

What would be three specific such "tools"?

I could just list categorical gadgets like limits and colimits, but presumably you were looking for more than that. Consider functors, adjunctions and monadicity. The first allows us to directly compare your category of graphs with another category, the second provides useful constraints on such a comparison, and the third guarantees and provides a construction of certain structures (including but not limited to limits and colimits) in your chosen category of graphs.

And all of those tools are just from an introductory text on category theory...

Alright, thanks. I don't see how adjunctions could yield new theorems in graph theory. The fact that adjoints preserve (co)limits is quite useful sometimes and can yield elegant proofs (the same is true for the Yoneda lemma), but I doubt it can do more than that. Most other concepts in basic category theory, such as limits, are only giving names to things.

Graham Manuell (Feb 23 2022 at 18:50):

Oh. Here's another example of category theory being useful in graph theory. I felt like this paper helped provide some insight about a result in graph theory which does involve graph homomorphisms, but which was first proved by László Lovász, who is a mainstream combinatorist. (Perhaps graph theorists would disagree, but I always found the similarity to the Yoneda lemma quite striking, so it was nice to see a formal explanation.)

Leopold Schlicht (Feb 23 2022 at 18:50):

Graham Manuell said:

I actually share some of the skepticism of exactly how useful graph theorists would find category theory. That said, there is at least one prominent example I can think of where it was arguably useful. Hedetniemi's conjecture was an open problem in graph theory for over 50 years before it was disproved in 2019. The counterexample uses the exponential object in the category of graphs.

Thanks for the example! In retrospect you might call his example an "exponential object in the category of graphs", but did Shitov really think about it that way when finding it? He doesn't use the words "category", "functor", "morphism", "universal property" in his text. One can invent direct products of groups without knowing it is called a "product in the category of groups". The same is true for "exponential object".

Graham Manuell (Feb 23 2022 at 18:54):

Yes, I agree that it's unclear that he thought about it as an exponential object, but it does seem like the universal property of the exponential played an important role in the counterexample whether it was thought of in explicitly categorical terms or not. If one concedes this was useful in this case it seems easier to believe that thinking about these things more systematically could provide further insights. Admittedly the chromatic number is one case where the utility of graph homomorphisms is particularly apparent.

Leopold Schlicht (Feb 23 2022 at 19:00):

Fair enough! Thanks again for your examples.

Morgan Rogers (he/him) (Feb 23 2022 at 19:11):

Leopold Schlicht said:

In retrospect you might call his example an "exponential object in the category of graphs", but did Shitov really think about it that way when finding it? He doesn't use the words "category", "functor", "morphism", "universal property" in his text. One can invent direct products of groups without knowing it is called a "product in the category of groups". The same is true for "exponential object".

Even supposing that Shitov was unaware that their constructions are special cases of categorical gadgets, doesn't that demonstrate that category theory is useful to graph theorists? Surely having to "invent" structures is more work than applying established constructions? You always can ignore that a construction is a special case of something more general, but you shouldn't: abstractions are what allow us to understand more precisely why and when things work!

Leopold Schlicht (Feb 23 2022 at 19:18):

Morgan Rogers (he/him) said:

Surely having to "invent" structures is more work than applying established constructions?

"Exponential object" is not a construction but a universal property. The explicit construction of an exponential object in a specific category doesn't need category theory. Of course it's really nice to have a name for that concept (exponential object), and it's interesting to investigate that concept in its own right, but I don't see how that demonstrates the usefulness of category theory.

Graham Manuell (Feb 23 2022 at 19:25):

I think Morgan saying that looking at exponential objects in the category of graphs would have lead them to the notion of exponential graphs, which they seem to agree are an important construction. (This might even be how they came to the definition of exponential graphs in the first place? I don't know the history.) Perhaps this construction could plausibly have been missed otherwise. And its links to chromatic number are certainly less obvious if you don't know the universal property.

Leopold Schlicht (Feb 23 2022 at 19:26):

Morgan Rogers (he/him) said:

Even lacking final evidence that using categories will be productive, its tools are pervasive, and their success is hard to deny.

Maybe that just applies to homological algebra and not to pure category theory?

Leopold Schlicht (Feb 23 2022 at 19:27):

Graham Manuell said:

I think Morgan saying that looking at exponential objects in the category of graphs would have lead them to the notion of exponential graphs, which they seem to agree are an important construction. (This might even be how they came to the definition of exponential graphs in the first place? I don't know the history.) Perhaps this construction could plausibly have been missed otherwise. And its links to chromatic number are certainly less obvious if you don't know the universal property.

Ah, I see, that makes sense!

Graham Manuell (Feb 23 2022 at 19:30):

Here's another rather silly example: the classification of epimorphisms in the category of planar graphs is related to the four-colour theorem in the sense that if you know the one result there is an easy proof of the other one. I'm not seriously suggesting this is an application of category theory to graph theory, and it certainly doesn't help with the proof, but since category theory is supposed to be helpful for suggesting good questions, it's perhaps at least worth noting that a natural categorical question ends up being essentially the same as a problem graph theorists agreed was a very important? (Link)

Benjamin Merlin Bumpus (he/him) (Feb 24 2022 at 14:31):

Paolo Perrone said:

Mike Shulman said:

Graph theorists certainly study graphs with "weights" on the edges, which you could call $\mathbb{R}$-enriched...

What are their morphisms? Or at least, which maps between them are relevant for the purpose of graph theorists?

graph theorist here..
There are no standard notions of homomorphisms between (what graph theorists call) labeled graphs. However, often you'll find that people will ask for some kind of non-decreasing property (assuming edges are labeled in $\mathbb{R}$, for example). Lots of graph theorists think about group-valued flows: flows on graphs whose edges are labeled by elements of some group. For examples, I suggest having a look at Geleen's work (and related things from U. Waterloo) or there also is a ton of material in Lex Schrijver's books (just to give a few reading hints).

Paolo Perrone (Feb 24 2022 at 15:21):

Thank you, this is very interesting!

Paolo Perrone (Feb 24 2022 at 15:26):

Benjamin Merlin Bumpus said:

However, often you'll find that people will ask for some kind of non-decreasing property (assuming edges are labeled in $\mathbb{R}$, for example).

Do you have an example of paper that does this? (Sorry, I'm really not an expert.)

Benjamin Merlin Bumpus (he/him) (Feb 24 2022 at 16:05):

Paolo Perrone said:

Thank you, this is very interesting!

Glad it helps :)

For the group-valued stuff, there's an example here: https://dl.acm.org/doi/10.1007/s00493-006-0030-1

For homomorphisms of edge-labeled graphs, there's really an abundance; a quick google gave me this paper (but I think it's best if you search for 'homo. of edge-labeled graphs' to find something more to your liking :) ): https://link.springer.com/article/10.1007/s10878-020-00680-3 which considers graph monos $f: (G,g) \to (H,h)$ such that g and h are edge-labelings of g and H resp. and f preserves 'colors' .

Another alternative is to consider homomorphisms between the quotients (see my paper with Kocsis, for example: https://arxiv.org/abs/2104.01841 )

Spencer Breiner (Apr 19 2022 at 18:29):

I'm trying to formulate networks of resistors using the algebraic path problem methodology, and I'm having a bit of trouble. More specifically, I'm having trouble ruling out (non-physical) loop currents.

We start with a quantale on $\R$ describing composition or resistors, with serial composition $R_1\cdot R_2=R_1 +R_2$ and parallel composition (join) $R_1\vee R_2 = (R_1^{-1} +R_2^{-1})^{-1}$. Then we hope to compute resistance in the network using an analogue of the free category construction.

In the simplest case we just have a graph X ---R--- Y. As a directed graph, there are arrows in both directions, so infinitely many paths from X to Y. However, when we compute the resistance between X and Y, we don't want to include any of the loops.

Following my nose, we ought to add in a reflexive loop at each nodes with zero resistance (edit: I guess this is the identity). This would short-circuit the computation of Hom(X,X) to yield zero, which seems promising. Then we go to compute Hom(X,Y), and I want to replace the infinite loopy sum with the hom-object Hom(X,X). Perhaps via quotient on the free category?

Anyway, I would be happy for either techinical suggestions or references to similar issues. Thanks!

John Baez (Apr 19 2022 at 18:40):

Do those two operations really give a quantale? A quick sketch of some circuits of resistors makes me doubt that series composition distributes over parallel composition (or vice versa).

John Baez (Apr 19 2022 at 18:41):

I've spent a certain amount of time trying to understand the algebraic structure of series and parallel composition, so if they obeyed the distributive law all this time and I didn't notice it, I'd feel like quite a fool. But I'd be happy if it were true!

John Baez (Apr 19 2022 at 18:43):

Maybe you know this paper on circuits made of resistors:

• John Baez and Brendan Fong, A compositional framework for passive linear networks.

This was our attempt to get to the bottom of things.

Spencer Breiner (Apr 19 2022 at 18:43):

Indeed, that approach is the basis for my question.

John Baez (Apr 19 2022 at 18:49):

Okay, great! Anyway, are you really saying your $\cdot$ operation distributes over $\vee$?

Spencer Breiner (Apr 19 2022 at 18:50):

It looks like the distributive law does indeed fail. It would say that we could push resistors through buses without changing the resistance b/w terminals, but it clearly would change resistances b/w terminals on the other side of the bus.

John Baez (Apr 19 2022 at 18:52):

Yes. One interesting thing is that $\cdot$ is $\vee$ conjugated by taking reciprocals (and vice versa). There should be some sort of algebraic way to think about this. In electrical circuit theory it winds up getting connected to Poincare duality for planar graphs. But it's still sort of mysterious.

Spencer Breiner (Apr 19 2022 at 18:53):

Nonetheless, it feels like there might be still be some relevant generalization. There is certainly a strong resemblance, in the calculations, since we are doing some kind of sum over possible paths.

John Baez (Apr 19 2022 at 18:54):

You're reminding me of some theorem where you compute the electrical resistance between two points on a network of resistors as a fancy sum.

John Baez (Apr 19 2022 at 18:55):

The name is on the tip of my tongue... let me go to a mirror and look at the tip of my tongue.

Spencer Breiner (Apr 19 2022 at 18:56):

Does it say something like: compute the resistance between X and Y from the neighbors of X -- X' and the resistances b/w X' and Y?

John Baez (Apr 19 2022 at 18:58):

It was something more complicated which might result from replying some rule like that over and over...

Spencer Breiner (Apr 19 2022 at 18:58):

Expanding the recursive calls on X'

John Baez (Apr 19 2022 at 18:59):

When I went to the mirror I saw the words Kirchoff's spanning tree theorem, but the Wikipedia article doesn't seem to explain the relevance to electrical circuits.

John Baez (Apr 19 2022 at 19:01):

The Wikipedia version is secretly about circuits where all the edges have resistance 1, so you get facts about about graph theory, but I think there's a version that lets the edges have arbitrary resistance.

Spencer Breiner (Apr 19 2022 at 19:03):

So each spanning tree gives a unique resistance b/w any pair of nodes, and then we sum over the set of spanning trees?

Reid Barton (Apr 19 2022 at 19:03):

There are some theorems about resistor networks and random walks which could be relevant

Spencer Breiner (Apr 19 2022 at 19:06):

Hmm. I suppose spanning trees are not nicely compositional, since we could decompose a network and break a spanning tree into several parts. I wonder if there is a nice generalization to spanning forests?

Spencer Breiner (Apr 19 2022 at 19:07):

@Reid Barton: I've seen something about Markov chains and the probabilities that a particular electron will take a particular path. Is that the sort of idea you've got in mind?

Reid Barton (Apr 19 2022 at 19:11):

Yes, this sort of thing.

Reid Barton (Apr 19 2022 at 19:13):

If you impose a voltage of 0 at a vertex $v_0$ and 0 at another vertex $v_1$, then the voltage potential at each vertex $w$ will be the probability that a random walk starting at $w$ will hit $v_1$ before $v_0$ (where the walk leaves a vertex through an edge with probability inversely proportional to the resistance of that edge, I guess).

Reid Barton (Apr 19 2022 at 19:13):

Then there is also some way to recast that in terms of the effective resistance between $v_0$ and $v_1$ which I don't remember.

John Baez (Apr 19 2022 at 19:14):

There's a really fun expository paper about resistor networks and random walks:

• Peter Doyle and J. Laurie Snell, Random walks and electric networks.

Graham Manuell (Apr 19 2022 at 20:45):

Besides the failure of distributivity, this also fails to be a quantale for the trivial reason that the 'join' is not idempotent.

John Baez (Apr 19 2022 at 20:54):

True.

John Baez (Apr 19 2022 at 20:55):

I guess I showed more than that it's not a quantale: it's not even a rig.

Zanzi (Apr 27 2022 at 14:30):

I remember looking into series-parallel operations and the algebraic path problem a while ago. AFAIK they don't form a rig, but they form something very close that Andrey Mokhov calls 'united monoids'. Here's a neat blog post on it: https://blogs.ncl.ac.uk/andreymokhov/united-monoids/