Counterexample to the conjectured coarse grid theorem
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911463562543104 |
|---|---|
| author | Albrechtsen, Sandra Davies, James |
| author_facet | Albrechtsen, Sandra Davies, James |
| contents | We show that for every $M,A,n \in \mathbb{N}$ there exists a graph $G$ that does not contain the $(154\times 154)$-grid as a $3$-fat minor and is not $(M,A)$-quasi-isometric to a graph with no $K_n$ minor. This refutes the conjectured coarse grid theorem by Georgakopoulos and Papasoglu and the weak fat minor conjecture of Davies, Hickingbotham, Illingworth, and McCarty.
Our construction is a slight modification of the recent counterexample to the weak coarse Menger conjecture from Nguyen, Scott and Seymour.
We further modify the construction to show that there are planar graphs that do not have the coarse Erdős-Pósa property. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_15342 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Counterexample to the conjectured coarse grid theorem Albrechtsen, Sandra Davies, James Combinatorics Metric Geometry 51F30, 05C83, 05C10, 05C70 We show that for every $M,A,n \in \mathbb{N}$ there exists a graph $G$ that does not contain the $(154\times 154)$-grid as a $3$-fat minor and is not $(M,A)$-quasi-isometric to a graph with no $K_n$ minor. This refutes the conjectured coarse grid theorem by Georgakopoulos and Papasoglu and the weak fat minor conjecture of Davies, Hickingbotham, Illingworth, and McCarty. Our construction is a slight modification of the recent counterexample to the weak coarse Menger conjecture from Nguyen, Scott and Seymour. We further modify the construction to show that there are planar graphs that do not have the coarse Erdős-Pósa property. |
| title | Counterexample to the conjectured coarse grid theorem |
| topic | Combinatorics Metric Geometry 51F30, 05C83, 05C10, 05C70 |
| url | https://arxiv.org/abs/2508.15342 |