MathDB

The Coarse Grid Theorem

About 1 year old · traced to

Let K,n∈NK,n \in \mathbb{N}. A graph has a KK-fat (n×n)(n\times n)-grid minor if it contains the corresponding fat minor model, and graphs are (M,A)(M,A)-quasi-isometric when they satisfy the stated coarse quasi-isometry bounds. Then there exist some M,A,g∈NM,A,g\in \mathbb{N} such that every graph with no KK-fat (n×n)(n\times n)-grid minor is (M,A)(M,A)-quasi-isometric to a graph of tree-width at most gg. 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.

References

Primary source

Sandra Albrechtsen and James Davies, “Counterexample to the conjectured coarse grid theorem”, arXiv:2508.15342 (2026).

coarse-graph-theoryfat-minorstree-width
Posted

Progress summary

Refreshed
Claimed solved

A preprint published in 2025 claims to give a counterexample, so the conjecture is regarded as refuted but the claim has not been independently verified.

The Coarse Grid Theorem, proposed by Georgakopoulos and Papasoglu, predicts that graphs avoiding a prescribed fat grid minor are uniformly quasi-isometric to graphs of bounded tree-width.

August 21, 2025 counterexample

Sandra Albrechtsen and James Davies claim that, for every M,A,n∈NM,A,n\in\mathbb{N} with M≥1M\geq 1, there is a graph whose (154×154)(154\times154)-grid is not a 33-fat minor, yet which is not (M,A)(M,A)-quasi-isometric to any graph with no KnK_n minor. Since bounded-tree-width graphs exclude sufficiently large clique minors, this would refute the theorem. The arXiv preprint makes this claim; no independent verification or correction was found in the retrieved sources.

Current status (as of September 2026): The conjecture is claimed refuted by the Albrechtsen–Davies counterexample, but the counterexample remains unverified in the retrieved record.

Sources

Solutions 0

No solutions have been posted yet.