The coarse Erdős-Pósa theorem

@misc{albrechtsen2026coarse,
  title = {{The coarse Erdős-Pósa theorem}},
  author = {Sandra Albrechtsen and Marthe Bonamy and Romain Bourneuf and James Davies},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.29414},
  eprint = {2609.29414},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.29414},
}

TY  - UNPB
TI  - The coarse Erdős-Pósa theorem
AU  - Sandra Albrechtsen
AU  - Marthe Bonamy
AU  - Romain Bourneuf
AU  - James Davies
PY  - 2026
DA  - 2026/09/24
PB  - arXiv
DO  - 10.48550/arxiv.2609.29414
UR  - https://arxiv.org/abs/2609.29414
AB  - We prove the coarse Erdős-Pósa conjecture of Georgakopoulos and Papasoglu. Informally, any graph either contains many fat cycles that are pairwise far apart, or there is a small number of bounded radius balls that together hit all of them. To be more precise, if G is a graph with no q-fat model of k · K_3 for some q, k ∈ ℕ, then there is a set X⊆ V(G) of 𝒪(klog k) vertices such that every q-fat model of K_3 in G has distance 𝒪(q) from X. In another form more closely resembling Manning's theorem that characterises quasi-trees: if G is a graph with no q-fat model of k · K_3 for some q, k ∈ ℕ, then G is 𝒪(q)-quasi-isometric to a graph H that contains a set X⊆ V(H) of 𝒪(klog k) vertices such that H−X is a forest. Bootstrapping this result, we further prove that every graph with no q-fat model of k · K_3 is quasi-isometric to a graph with no k · K_3 minor, where the quasi-isometry can be chosen to only have additive distortion. This result also holds for k = ∞. We also obtain an Erdős-Pósa theorem for long induced cycles that are far apart.
ER  -