Does planarity qualify as a "local condition?" I'd think it should, but I don't see how to put it into the "data on small/local subgraphs" framework.
Anyway, if it does, you have of course the four-color theorem, and even better the five-color theorem, whose proofs essentially take advantage of the fact that we sort of understand how to move between "local" and "global" in topological spaces.
ETA: More generally, of course, there's the whole subfield of "structural graph theory" and its methods. I don't know that the graph minor theorem is "local-to-global" -- it's really more "local-to-a-different-kind-of-local" -- but it's probably the most important structural result.
Structural graph theory is something that I wish I knew about, but looks so horrifically technical and difficult that I'm sort of afraid to study it. There are clearly some deep patterns hidden there, though -- witness how Robertson, Seymour, and Thomas all worked on the proof of the Strong Perfect Graph Conjecture, which used a decomposition argument and had a hugely structural flavor despite being (as far as I can tell) mostly unrelated to the more topological work they'd previously done.
Tangentially, this recent preprint of Dvorak, Kral and Thomas caught my eye for exactly the "local properties" reason. Unfortunately the proof of the main theorem doesn't seem to be available yet...
No comments:
Post a Comment