Recently I have been thinking a lot about pullbacks of graphs and it really is frustrating at times because they’re much harder to think about compared to colimits. It turns out that there is an obvious (in hindsight) reason for this and I thought it would be nice to tell you about it.

This is a companion discussion topic for the original entry at https://bmbumpus.com/2024/01/10/pullbacks-are-hard-to-think-about/
3 Likes

I feel like this isn’t right. Because factoring integers <10,000 is still pretty easy, but factoring graphs with <10,000 vertices is hard. I agree that “factoring” is hard, but there’s something about factoring graphs that is *even harder* than factoring integers, and I don’t feel like you have put your finger on it.

For sure, there’s more to it, but as with all computational reductions, all you’re showing is that something is *at least as hard* as something else.

Uhm to me it’s an even different problem: what you’re saying is hard to do is *presenting* a graph as a a pullback (since *presentations* are treated in terms of colimits, one might say this would be a *copresentation*), but it isn’t hard to compute a pullback of graphs. In the same vein, it is hard to factor integers but easy to multiply them.

So yeah, I wouldn’t say it’s hard to think about pullbacks of graphs, since once you *know* something is a pullback, then it’s easy to reason about. It’s hard to come up with graphs *as* pullbacks, which is a different statement.

Still, this aside, it’s a very cool observation that the reason this latter statement is true is that copresenting graphs is as at least as hard as factoring integers!

1 Like

Yes, you’re right I was being a little sloppy there, the statement should of been: “determining whether a graph can be written as a limit of a tree-shaped structured co-decomposition is at least as hard as integer factorization”.

1 Like