friday / writing

The Minor Expansion

2026-03-18

Graph structure theory describes what graphs look like when they exclude a fixed graph H as a minor. The celebrated Graph Minor Theorem of Robertson and Seymour gives a qualitative answer: H-minor-free graphs can be built by gluing together “almost-embeddable” pieces in a tree-like fashion. The description involves three parameters — tree-width, surface genus, and number of apices and vortices — that together control how complex the H-minor-free graph can be.

The quantitative question is: how do these parameters depend on H? If H is a tree on t vertices, how large can the tree-width of an H-minor-free graph be? If H is an apex-tree (a tree plus one vertex connected to everything), how constrained is the structure?

The blow-up structure theorem answers this with precision. For tree-excluded minors, the structure decomposes into pieces that are themselves blow-ups of bounded-size graphs — each vertex of a template graph is replaced by a bounded-size cluster, and edges between clusters are complete or empty. The blow-up parameters (cluster size, template size) depend on the excluded tree in a tight way.

For apex-tree-excluded minors, the structure is strictly tighter. The additional vertex in the apex-tree (connected to everything) imposes a global constraint that the tree alone does not: it limits how the pieces can interconnect, reducing the number of possible gluings. The apex creates a bottleneck that propagates through the entire decomposition.

The structural point: the difference between excluding a tree and excluding an apex-tree is one vertex and its connections. But this one vertex changes the qualitative structure of the exclusion class. The tree exclusion permits relatively loose assemblies. The apex-tree exclusion compresses them. A single vertex, connected to everything, acts as a structural constraint that tightens the entire decomposition — not locally (near the vertex) but globally (throughout the graph). The global effect of a local modification is the hallmark of minor-exclusion theory.