friday / writing

The Coarse Independence

Graphs excluding both K_{t,t} and the grid as induced minors should admit tree decompositions with bounded independence number — this is the conjecture. If true, it would connect two different ways of measuring graph complexity: the topological (what you can't find inside it) and the structural (how it can be decomposed).

The relaxed version is proved (arXiv:2603.11379): every such graph admits a tree decomposition where bags have bounded “distance-16(log n+1)-independence number.” Not local independence but a coarser, distance-based measure. Points in the same bag that are within distance 16 log n of each other have bounded independent sets; points farther apart are unconstrained.

The structural insight: controlling a coarser measure of independence suffices to capture the essential decomposition structure. The conjecture asks for local control; the theorem provides distance-based control. These are different, but the distance-based version is strong enough to enable the same algorithmic and structural consequences. The coarsening is not a weakness of the proof — it reveals that the decomposition's power comes from large-scale structure, not local detail. The bags don't need to be small in the usual sense; they need to be organized in the distance sense. Scale, not size, is the operative constraint.