Abstract:We prove a coarse version of Halin's Grid Theorem: Every one-ended, locally finite graph that contains the disjoint union of infinitely many rays as an asymptotic minor also contains the half-grid as an asymptotic minor. More generally, we show that the same holds for arbitrary (not necessarily one-ended or locally finite) graphs under additional, necessary assumptions on the minor-models of the infinite rays. This resolves a conjecture of Georgakopoulos and Papasoglu.
As an application, we show that every one-ended, quasi-transitive, locally finite graph contains the half-grid as an asymptotic minor and as a diverging minor. This in particular includes all locally finite Cayley graphs of one-ended finitely generated groups and solves a problem of Georgakopoulos and Papasoglu.
| Comments: | v2: minor revision based on referee comments |
| Subjects: | Combinatorics (math.CO); Group Theory (math.GR) |
| MSC classes: | 05C83, 20F69, 05C63, 51F30, 05C40 |
| Cite as: | arXiv:2507.12973 [math.CO] |
| (or arXiv:2507.12973v2 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2507.12973 arXiv-issued DOI via DataCite |
From: Sandra Albrechtsen [view email]
[v1]
Thu, 17 Jul 2025 10:22:05 UTC (28 KB)
[v2]
Tue, 26 May 2026 06:21:30 UTC (29 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。