Pullbacks are Hard to Think About!
Benjamin Bumpus
Wed Jan 10 2024
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/
Owen Lynch
Wed Jan 10 2024
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.
Benjamin Bumpus
Wed Jan 10 2024
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.
Matteo Capucci
Thu Jan 11 2024
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!
Benjamin Bumpus
Thu Jan 11 2024
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”.