The Coarse Grid Theorem

Let $K,n \in \mathbb{N}$. A graph has a $K$-fat $(n\times n)$-grid minor if it contains the corresponding fat minor model, and graphs are $(M,A)$-quasi-isometric when they satisfy the stated coarse quasi-isometry bounds. Then there exist some $M,A,g\in \mathbb{N}$ such that every graph with no $K$-fat $(n\times n)$-grid minor is $(M,A)$-quasi-isometric to a graph of tree-width at most $g$. Coarse Grid Theorem.

The conjecture was proposed as a coarse analogue of the Robertson–Seymour grid theorem. It is refuted by the counterexample constructed in this paper, which supplies graphs without the specified fat grid minor that are not quasi-isometric to graphs of bounded tree-width.