More on grid minors

I made a preprint out of my earlier post here on grid minors in damaged grids: it is arXiv:1303.1136.

Somewhere along the way I learned of an interesting related result in infinite graph theory, Halin's grid theorem. In finite graphs the size of the largest grid minor is bounded above and below by (two different) functions of the treewidth, and the treewidth of a finite graph may be characterized by the maximum order of a haven, a certain kind of strategy for a cops-and-robbers game on the graph. In infinite graphs this breaks down, because a haven with infinite order exists whenever the graph has an infinite path (even if its treewidth is one and it has no nontrivial grid minors). Rather, the infinite-order havens correspond to the ends of the graph (equivalence classes of infinite paths that, intuitively, all go the same direction, in the sense that one can bounce back and forth between any two equivalent paths infinitely often). An end is "thick" if it includes an infinite set of disjoint paths, and Halin's theorem states that a graph has a thick end if and only if it has an infinite grid minor.

Because of the tight connections between havens, treewidth, and grid minors in finite graphs, and the less-direct but still present connections between havens, ends, and infinite grid minors, it makes me think that maybe there should be something like a haven but more constrained, or a different parameterization of havens than their order, that should work for both finite and infinite graphs, that gives both upper and lower bounds on the size of the grid minor for graphs in which this is bounded, and that could distinguish those graphs from the graphs in which all grid minors are finite but with unbounded size, and from the graphs with infinite grid minors.

Comments: