PaperlayerView exact revision on arXiv

Source-linked AI summary

The coarse Erd\H{o}s-P\'{o}sa theorem

Sandra Albrechtsen, Marthe Bonamy, Romain Bourneuf, James Davies

arXiv:2609.29414v1math.COcs.DMmath.MG

TL;DR

The paper addresses the question of whether excluding many well-separated fat triangle models yields a small hitting set or a forest-like model. It develops local tree-like decompositions around selected cycles and proves both forms of this alternative, while noting that the hitting-set result does not extend to planar minors.

  • Problem

    The paper considers whether excluding k well-separated fat triangle models allows a small set to come close to every fat triangle model.

    Source: §1 · p. 2

  • Method

    The proof selects fat cycles and uses locally tree-like regions and corsola cycles to build the required structure.

    Source: §3 · p. 10

  • Results

    If G has no q-fat model of k · K3, it is quasi-isometric at scale proportional to q to a graph made into a forest by deleting f1.1(k) vertices.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper also proposes extending the fat-minor quasi-isometry result to every forest, including an additive-error version.

    Source: §12 · p. 69

    The hitting-set theorem for fat triangle models cannot be extended to planar minors.

    Source: §1 · p. 2

Abstract

from arXiv · show

We prove the coarse Erd\H{o}s-P\'{o}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 \cdot K_3$ for some $q, k \in \mathbb{N}$, then there is a set $X\subseteq V(G)$ of $\mathcal{O}(k\log k)$ vertices such that every $q$-fat model of $K_3$ in $G$ has distance $\mathcal{O}(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 \cdot K_3$ for some $q, k \in \mathbb{N}$, then $G$ is $\mathcal{O}(q)$-quasi-isometric to a graph $H$ that contains a set $X\subseteq V(H)$ of $\mathcal{O}(k\log 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 \cdot K_3$ is quasi-isometric to a graph with no $k \cdot K_3$ minor, where the quasi-isometry can be chosen to only have additive distortion. This result also holds for $k = \infty$. We also obtain an Erd\H{o}s-P\'{o}sa theorem for long induced cycles that are far apart.

1 A Long-expected Party

The paper proves a coarse Erdős–Pósa result for fat triangle models, with both a bounded-size hitting set and a quasi-isometric forest structure. It also gives extensions to far-apart long cycles, minor-free models, asymptotic dimension, and metric spaces.

1 A Long-expected Party

  • O(k log k) vertices suffice for a set whose deletion from a quasi-isometric model leaves a forest, with quasi-isometry scale proportional to q.The theorem applies when G has no q-fat model of k · K3.Source: §1 · p. 2
  • O(k log k) vertices can be chosen so every q-fat model of K3 lies within distance O(q) of that set.This applies when G has no q-fat model of k · K3.Source: §1 · p. 2
  • The hitting-set theorem for fat triangle models cannot be extended to planar minors, unlike the classical Erdős–Pósa theorem.The paper identifies this as a contrast with the planar-minor extension of the classical theorem.Source: §1 · pp. 1–2
  • O(k log k) vertices suffice to bring every long cycle, or every long induced cycle, within distance O(max{ℓ, q}) of a set when k such cycles cannot be pairwise q-distant.The two results treat ordinary cycles and induced cycles separately.Source: §1 · p. 3
  • Graphs with no q-fat model of k · K3 are (1, f1.6(k, q))-quasi-isometric to graphs with no k · K3 minor.The authors obtain this by bootstrapping their forest-structure result; the quasi-isometry has only additive error.Source: §1 · p. 3
  • The infinite version also holds: excluding a q-fat model of ∞·K3 yields a (1, f1.7(q))-quasi-isometry to a graph with no ∞·K3 minor.The forest-structure theorem’s quasi-isometry bounds do not depend on k, despite giving a less precise structure.Source: §1 · pp. 3–4
  • For every q and k, graphs with no q-fat model of k·K3 have asymptotic dimension at most 1.The paper also states this for a graph with no q-fat model of ∞·K3.Source: §1 · p. 4
  • For length spaces, the paper relates quasi-isometry to a graph with a vertex whose deletion leaves a tree to exclusion of fat K3 models.For proper geodesic metric spaces, being quasi-isometric to a tree is equivalent to excluding K3 as a q-fat minor for some q.Source: §1 · p. 4

2 Preliminaries

The preliminaries fix notation for distances, balls, fat-minor models, quasi-isometries, and graph-decompositions. They also state how bounded-width and bounded-spread decompositions relate to quasi-isometries.

2 Preliminaries

  • Graphs may be infinite; N denotes the positive integers, [n] the first n positive integers, and Zn denotes Z/nZ.The paper allows infinite graphs unless stated otherwise.Source: §2 · p. 5

2.1 Distance, radius and balls

  • Distance is shortest-path length, and BG(U, r) is the set of vertices at distance at most r from U.The radius of a vertex set is the least radius of a ball containing it, or infinity if none does.Source: §2.1 · p. 5

2.2 Fat minors

  • A q-fat model uses disjoint connected branch sets and internally disjoint branch paths, with distance at least q between non-incident model elements.A q-fat cycle is a cycle divisible into six paths whose non-consecutive paths are at distance at least q.Source: §2.2 · pp. 5–6

2.3 Quasi-isometries and graph-decompositions

  • Graph-decompositions index vertex bags by a graph; bounded radial width and spread are equivalent to quasi-isometries with bounded parameters.Radial width bounds bag radii in the original graph, while radial spread bounds the radii of vertices’ connected sets of bag indices.Source: §2.3 · pp. 6–7

3 Proof sketch and overview

The proof centers on a structural decomposition: excluding a q-fat model of k · K3 yields a graph-decomposition with bounded-radius bags and a large-girth decomposition graph. The sketch builds this decomposition from carefully selected cycles, then uses far-apart cycles in the decomposition graph to derive the Erdős–Pósa conclusions.

Structural statement

  • If G excludes a q-fat model of k · K3, it admits a graph-decomposition with bounded-radius bags modelled on a graph of girth much larger than q.This structural statement is the proof’s central target.Source: §3 · p. 8

Deriving the conclusions

  • Large girth lets cycles in the decomposition graph be converted into fat cycles and lifted to G, reducing the problem to finding distant ordinary cycles.The Erdős–Pósa result of Dujmović, Joret, Micek, and Morin then gives either many distant cycles or a small set whose neighborhood leaves a forest.Source: §3 · pp. 8–9

Cycle selection

  • The construction first packs pairwise distant q-fat goldfish cycles, then corsola cycles, leaving a remainder with a tree-decomposition of small-radius bags.Goldfish cycles lie in a bounded-radius ball; corsola cycles have a long tree-like region and a short remaining path.Source: §3 · pp. 9–10

Combining regions

  • The graph is organized into bounded-radius goldfish regions, single-long-cycle corsola regions, and a remainder admitting a tree-decomposition.Enlarging the remainder’s neighborhood allows its decomposition to overlap the corsola decompositions in a controlled way.Source: §3 · pp. 10–11
  • Controlled overlaps combine the regional decompositions without creating short cycles in the decomposition graph, while keeping every bag’s radius small.The resulting graph-decomposition has large girth, as required by the structural statement.Source: §3 · pp. 8, 11

Proof roadmap

  • The proof sketch assigns Sections 4–7 to local decompositions, corsola-cycle selection, handling distances between selected cycles, and combining decompositions.Section 8 combines these ingredients to prove the structural statement; Section 9 completes Theorems 1.1 and 1.2 and proves the long-cycle corollaries.Source: §3 · p. 11

4 The forest-decomposition lemma

The forest-decomposition lemma turns the condition that every q-fat model of K3 lies near a prescribed set into a partial forest-decomposition away from a larger neighborhood. Its proof contracts the nearby region, uses a K4-minor-free decomposition, and transfers the resulting forest structure back to G.

Lemma 4.1

  • If every q-fat model of K3 in G lies within distance d of U, then G has an honest partial forest-decomposition supported outside a radius r4.1(q,d) neighborhood of U.The decomposition’s radial width and spread depend only on q.Source: §4 · pp. 12–13

Proof strategy

  • A graph with no q-fat K4 model admits an honest radial graph-decomposition modelled on a K4-minor-free graph.The cited theorem supplies parameters 25235q + 71 and 22 for radial width and spread, respectively.Source: §4 · pp. 12–13

Cycle lifting

  • A sufficiently fat cycle in the decomposition graph yields a q-fat cycle in G within a bounded neighborhood, while preserving separation from distant vertices.Lemma 4.4 requires q′ ≥ 2r2(q + 1) + 4r1r2; vertices whose decomposition nodes are more than q′ from the cycle remain more than q away from its lifted cycle.Source: §4 · p. 12

Proof strategy

  • After deleting a sufficiently large ball around the node representing the contracted vertex, the decomposition graph has no q′-fat cycle.The proof establishes this by ruling out a (3q′)-fat cycle outside that ball.Source: §4 · pp. 13–14
  • Contracting B_G(U,d) to one vertex makes every q-fat model of K3 contain that vertex, so the contracted graph has no q-fat model of K4.A K4 model avoiding the contracted vertex would contain a K3 model avoiding it.Source: §4 · pp. 13–14

2. Since (H, V′) has radial spread at most r′

The proof rules out a sufficiently fat cycle in the decomposition graph outside a ball around the node representing the contracted set. A separator argument and cycle-lifting lemma would otherwise produce a forbidden q-fat model of K3 in the contracted graph.

Claim 4.5

  • A q-fat cycle in H outside the specified ball would lift to a q-fat model of K3 in G/W avoiding w, contradicting that every such model contains w.This contradiction supports the claim that H minus the ball has no (3q′)-fat cycle.Source: §2 · p. 14
  • If the alleged (3q′)-fat cycle is not q′-fat in H, two nonconsecutive witness paths lie within distance q′, forcing a short connecting path that intersects the ball.The K4-minor-free property gives a two-vertex separator between the ball and the cycle.Source: §2 · p. 14
  • The separator yields paths R′ and S′ that avoid the smaller ball and form a fat K3 model in H.The proof divides S′ into seven edge-disjoint subpaths and combines selected subpaths with R′ to construct the model.Source: §2 · pp. 14–15
  • The constructed model remains far enough from w to lift to a q-fat K3 model in G/W that avoids w.Lemma 4.4 supplies the lift, contradicting the contraction argument.Source: §2 · p. 15

Forest-decomposition construction

  • The proof then uses ρ to enlarge the excluded neighborhood and obtains a partial forest-decomposition supported outside B_G(U, ρ + d).That support set is Y, and the resulting decomposition is transferred back to G.Source: §2 · p. 15

5 The happy hippo lemma (aka Finding a corsola cycle)

This section develops the happy hippo construction, turning a sufficiently distant q′-fat cycle with no nearby q-fat K3 models into a distant q-fat corsola cycle using controlled geodesic jumps, a protected shortcut, and a buffer. A local decomposition lemma verifies the hypotheses needed for the construction by providing a partial tree-decomposition supported on BG(PC′, t) with the required radial width and spread for C′.

5 The happy hippo lemma (aka Finding a corsola cycle)

  • A (r1, r2, t, κ)-corsola cycle splits into internally disjoint paths PC and WC, with WC short, a decomposition supported near PC, and controlled distances along PC.The conditions require WC length at most 77t, an (r1, r2)-radial partial tree-decomposition supported on BG(PC,t), and dPC(u,v) ≤ 4τ + κ whenever dG(u,v) ≤ τ ≤ t.Source: §5 · p. 16
  • Under its stated distance and local-exclusion conditions, Lemma 5.2 guarantees a q-fat corsola cycle whose path component stays at least q from U.For t ≥ 5q + 3, the input cycle is q′-fat and at distance at least a5.2(q) from U; every ball of radius b5.2(q,t) around it contains no q-fat K3 model.Source: §5 · p. 16
  • The cited passage states that G admits a (w5.3(q, ε), s5.3(ε))-radial partial tree-decomposition with support BG(P, t), specifying its width and spread parameters.Source: §5 · p. 16
  • The decomposition proof layers BG(P,t) into 5q-near-components, which form a tree around P because components have bounded diameter and unique predecessors beyond layer 5q.The construction uses component-neighborhood bags and path-centered bags; it yields radial spread 3ε + 2 and radial width max{10q + 1, ε + 5q + 2}.Source: §5 · pp. 17, 20, 21

Lemma 5.10

  • Lemma 5.10 constructs length-ℓ geodesic jumps from a q′-fat cycle, with each jump after the first avoiding the preceding radius-r buffer.It assumes r ≥ 10q, ℓ > 8r, q′ > ℓ + 1, and no q-fat K3 model in any radius-ℓ ball centered on C.Source: §5 · p. 21
  • Before the last jump, every length-at-most-L path from v_i to an earlier jump-sequence vertex meets the buffer; termination supplies a final such path avoiding it.The buffer is BG(o_i, r/2), and the final avoiding path has length at most L.Source: §5 · p. 21

Lemma 5.2

  • Under Lemma 5.2’s assumptions, a sufficiently distant locally sparse q′-fat cycle yields a q-fat corsola cycle C′ whose path PC′ remains at distance at least q from U.The assumptions include t ≥ 5q + 3 and the absence of q-fat K3 models in specified-radius balls around C.Source: §5 · p. 24

Proof of Lemma 5.2

  • The final avoiding shortcut supplies WC′, while a jump-sequence subpath supplies PC′; a protected geodesic segment in its buffer witnesses q-fatness, and d(PC′, U) ≥ q.The protected segment has length r ≥ 5q; the construction stays close enough to C to retain the stated distance from U.Source: §5 · pp. 24, 26
  • The construction gives WC′ length at most 77t and, under (C3)’s stated range, bounds PC′ distance by 4τ + κ when ambient distance is at most τ.Applying Lemma 5.3 to PC′ supplies the partial tree-decomposition required by (C2).Source: §5 · pp. 24, 26

5 The happy hippo lemma (aka Finding a corsola cycle)

  • Every vertex of PC′ lies within distance ℓ of C, so no q-fat model of K3 is contained in its radius-b′ ball.This verifies the locally tree-like hypothesis, since b′ = b − ℓ.Source: §5 · p. 27
  • For u, v on PC′ with dG(u, v) ≤ 20q + 4, a shortest-path shortcut contradicts condition (3) if dPC′(u, v) > 2ℓ.Thus PC′ is locally almost geodesic, with nearby vertices at distance at most 2ℓ along PC′.Source: §5 · p. 27
  • The (C3) bound implies that dPC′(u, v) ≤ b′ whenever dG(u, v) ≤ 2t + 15q, verifying the no-long-shortcut hypothesis.The bound used is b′ = 8t + 60q + κ.Source: §5 · p. 27
  • Lemma 5.3 gives G a partial tree-decomposition supported on BG(PC′, t), with radial width w5.2(q) and radial spread s5.2(q), proving (C2) for C′.Here C′ = PC′ ∪ WC′.Source: §5 · p. 27

6 Untangling corsola cycles

The untangling lemma either finds a q-fat model of k·K3 or a small set whose bounded-radius balls meet every sufficiently short path between the separated corsola paths. Its proof converts a large family of separated paths into a graph where disjoint cycles yield q-fat cycles in G.

6 Untangling corsola cycles

  • For pairwise-more-than-5q-separated (·, ·, t, κ)-corsola paths with t ≥ 2q, either G contains a q-fat model of k·K3, or some X has size at most 2n + 24k log k and every inter-path path of length less than d meets BG(X, R6.2(q, d, κ)).Source: §6 · p. 28
  • A maximal collection of geodesic inter-path connectors, separated by at least R−2d, gives the small hitting set when its size is at most n+12k log k.Taking the connectors’ endpoints yields |X|≤2n+24k log k and the required ball-hitting property.Source: §6 · p. 28
  • If the connector collection is larger, the proof builds paths J and endpoint set X with |X|>2n+24k log k, then forms a maximum-degree-3 graph H whose degree-3 vertices lie in X.The construction uses geodesic connector segments and subpaths of the original corsola paths; distinct paths in the resulting collection are pairwise at least q apart.Source: §6 · pp. 28–29
  • Disjoint cycles in H are pairwise at least q apart in G and each is a q-fat cycle, so more than 24k log k degree-3 vertices force k disjoint cycles and hence a q-fat model.The proof obtains the degree-3 threshold after deleting degree-at-most-1 vertices, then applies Simonovits’s theorem.Source: §6 · pp. 27, 29

7 Smooshing the tree-decompositions together

This section constructs a graph-decomposition by modifying and gluing forest-decompositions around distant corsola paths and selected regions, controlling the interfaces and radial parameters to obtain a modelled graph of girth at least g.

7 Smooshing the tree-decompositions together

  • Lemma 7.1 combines decompositions around pairwise-distant corsola paths with a radial partial forest-decomposition into a radial partial graph-decomposition of girth at least g, supported on BG(P,z) ∪ C.The paths are (r1,r2,z)-corsola and pairwise at distance at least d7.1(z); the forest-decomposition has support BG(C,y7.1(r1,g)), and z must be at least z′7.1(r1,g).Source: §7 · p. 30

Preparation

  • The preparation restricts the two forest-decompositions, contracts components near the path annulus, then identifies corresponding nodes; separation in GC ensures the resulting decomposition graph has girth at least g.Distinct identified components have interface vertices at distance roughly at least 2z2 in GC, forcing their corresponding nodes in the GC decomposition far apart.Source: Preparation · p. 32

Definition of the forest-decomposition (eTP, eVP)

  • The interface Y equals V(GP) ∩ V(GC); distinct YO sets are at distance at least 2z1 − 4r1, and paths between them avoiding the specified inner ball have length greater than 2z2.Within each UO, every pair of vertices has a path through BG(P,z − z2 + 2r1) of length at most 2z1 + 6r1.Source: Definition of the forest-decomposition… · pp. 33–34
  • In the eTP construction, every y–y′ path avoiding BG(P, z − z1 − z2 + 2r1) has length greater than 2z2, and each component O is contracted to a node.Source: Definition of the forest-decomposition… · p. 35

Definition of the forest-decomposition (eTC, eVC)

Definition of the graph-decomposition (H, V)

8 Coral reef (aka Packing many fat cycles)

Section 8 establishes a structural alternative: either G contains a q-fat model of k·K3, or a decomposition with a small set of vertices controlling short cycles and bounded-radius bags elsewhere. Its construction extends a partial forest-decomposition to obtain the latter outcome.

8 Coral reef (aka Packing many fat cycles)

  • Either k·K3 is a q-fat minor of G, or a graph H has a small set U hitting every cycle of length at most g and supports a radial decomposition of G with bounded-radius bags outside U.The size bound is f8.1(k) = O(k log k); the decomposition parameters and bag-radius bound depend on q and g.Source: §8 · p. 38

Preparation

  • The proof first selects pairwise separated q-fat goldfish cycles, then recursively builds corsola cycles forming a coral reef; enough cycles yield outcome (i), while termination yields outcome (ii).The recursive construction is designed so that goldfish and corsola cycles remain appropriately separated, and the cycles satisfy the coral-reef conditions.Source: Preparation · pp. 39, 41, 42
  • A coral reef of n controlled-interaction corsola cycles contains at least n/79 cycles pairwise at distance at least q.The construction uses this extraction to obtain the desired separated cycles from a reef of size 79(k − m).Source: Preparation · pp. 39, 40, 42
  • Finding 79(k−m) corsola cycles yields a q-fat model of k · K3; otherwise, termination provides the partial forest-decomposition used for outcome (ii).At each step, a newly added corsola cycle preserves the coral-reef conditions and admits a set Yn+1 of at most N(n + 1) vertices satisfying (A3).Source: Preparation · pp. 44–45

Construction of the graph-decomposition (outcome (ii))

  • To build outcome (ii), the proof trims corsola paths to make them pairwise far apart, combines their partial tree-decompositions with the forest-decomposition, then applies Lemma 7.1.The remaining uncovered vertices lie within bounded distance of XDn, Yn and Z and are covered by additional bounded-radius bags.Source: Construction of the… · p. 45
  • The resulting graph-decomposition has radial width and spread depending only on q, and its underlying graph H′ has a set U of at most f8.1(k) vertices such that H′−U has girth at least g + 1.The added bags have radius independent of k.Source: Construction of the… · p. 47

9 Proof of coarse Erdős-Pósa (Gotta catch ’em all)

The section establishes a coarse Erdős–Pósa packing-or-hitting-set dichotomy for cycle collections containing all q-fat cycles, with an O(k log k) hitting-set bound. It also proves a quasi-isometry to a graph that becomes a forest after deleting O(k log k) vertices.

9 Proof of coarse Erdős-Pósa (Gotta catch ’em all)

  • For any cycle collection containing all q-fat cycles, either k cycles are pairwise at distance at least q, or O(k log k) vertices lie within O(q) of every cycle.The hitting-set size is at most f9.1(k), with f9.1 ∈ O(k log k), and the distance bound is d9.1 · q.Source: §9 · p. 47

9.1 Turning cycles of H into fat cycles of G

  • A cycle in H at distance at least 5q/2 + 1 from U yields a q-fat cycle within distance 5q/2 of it.This applies when U meets every cycle of H of length at most 30q + 5.Source: §9.1 · p. 49
  • In an honest decomposition with bounded radial spread and bounded-radius bags outside U, a sufficiently distant cycle in H lifts to a nearby q-fat cycle in G.The lifting lemma gives thresholds and a containment radius depending on q, r1, and r2.Source: §9.1 · pp. 49–50

9.2 Finding/Hitting cycles in a tree-decomposition

  • For cycles supported by a partial forest-decomposition, either k members are pairwise q-distant or fewer than k vertices lie within a bounded distance of every member.The tree lemma underlying this dichotomy requires the connected subgraphs of the forest to have finite radius; it gives either a hitting set of size less than k or k pairwise disjoint members.Source: §9.2 · p. 51

9.3 Proof of Theorem 9.1

  • The auxiliary cycle theorem gives either k cycles at pairwise distance greater than d or a set of O(k log k) vertices whose c9.7 · d-neighborhood leaves a forest [CDJ+26].The proof outline applies a decomposition dichotomy, transfers distant cycles from H to q-fat cycles in G, and converts a forest after deleting bounded-radius neighborhoods into a hitting set.Source: §9 · p. 48, §9.3 · p. 52
  • If G has no q-fat model of X, its q-th power has no 3-fat model of X, and G is q-quasi-isometric to that power.A 3-fat model in the q-th power also yields a q-fat model in G within distance ⌈q/2⌉.Source: §9.3 · p. 52
  • Either C contains k cycles pairwise at distance at least q, or a set of at most f9.1(k) vertices lies within distance d9.1·q of every cycle in C.The collection C must contain all q-fat cycles, and f9.1(k) can be chosen in O(k log k).Source: §9.3 · p. 52
  • The hitting-set size can be bounded by O(k log k).Source: §9.3 · pp. 52–53

9.4 Quasi-isometries

  • If G has no q-fat model of k·K3, it is (λ1.1·q)-quasi-isometric to H, where deleting at most O(k log k) vertices leaves a forest.Source: §9.4 · p. 54

10 The Scouring of the Shire

Section 10 proves the fat minor conjecture for H = k · K3, including k = ∞, and completes the associated forest-path dichotomy. It also refines the quasi-isometry results to additive error, including constructing a graph additively quasi-isometric to G with no infinite K3 minor; by [GP25, Lemma 5.3], the conjecture then holds for arbitrary disjoint unions of cycles.

10.1 The fat minor conjecture for disjoint unions of cycles

  • For k = ∞, a graph with no q-fat model of ∞ · K3 is (λ10.1 · q)-quasi-isometric to a graph with no ∞ · K3 minor.The proof constructs an infinite q-fat model if every finite number of pairwise separated triangles occurs as a 3q-fat minor.Source: §10.1 · p. 56
  • For finite k, a graph with no q-fat model of k · K3 is (f10.2(k) · q)-quasi-isometric to a graph with no k · K3 minor.The proof reduces the problem to graphs whose deletion of a set of at most m vertices leaves a forest, then uses bounded-depth contractions.Source: §10.1 · p. 56
  • With G − X a forest and |X| ≤ m, if G has no q-fat model of k · K3, a bounded-depth contraction-minor has no k · K3 minor.The contraction depth is bounded by f10.4(m, q, k).Source: §10.1 · p. 57
  • If every q-fat model of k · K3 intersects Y, a bounded-depth contraction-minor has no k cycles separated by 6q + 3 and at least 5q/2 + 1 from YH.This strengthens the contraction step by retaining the requirement that cycles remain far from the image of Y.Source: §10.1 · p. 57
  • For graphs with forest remainder G − X, bounded-depth contractions eliminate k disjoint cycles, by eliminating each feasible type through contractions away from X.Feasible types encode cycle paths through X and a partition of X; Lemma 10.6 then yields a contraction-minor with no k disjoint cycles.Source: §10.1 · pp. 58–59
  • For plentiful path collections in a forest, either representatives can be chosen pairwise q-distant, or a bounded-edge subforest connects a pair from every choice of representatives.The subforest intersects each path of the forest in at most f10.8(r, q) edges.Source: §10.1 · p. 60
  • For m collections of m subtrees in a forest, each internally q-separated, one can select a subtree from each collection so the selections are pairwise q-separated.This is Lemma 10.9, used to combine far-apart paths found within collections.Source: §10.1 · p. 61
  • For plentiful subpaths in a forest that is a union of at most ℓ paths, either at most 4ℓ^2(q+1)r subpaths cover every member by containment, or r paths are pairwise q-distant within a common subpath.Source: §10.1 · p. 61
  • For plentiful subpath collections in a forest, either representatives are pairwise q-distant, or a bounded-edge subforest connects representatives from two collections in every selection.The subforest J has at most f10.8(r, q) edges on any path of F.Source: §10.1 · p. 62

10.2 Additive quasi-isometries

  • G is (1, f1.6(k, q))-quasi-isometric to a graph with no k·K3 minor when G has no q-fat model of k·K3.The target graph is obtained by contracting and subdividing edges, operations that do not create new cycles.Source: §10.2 · p. 64
  • For the infinite-packing case, the proof improves the forest part to additive error and uses a finite shortcut set to extend the map while keeping the target ∞·K3-minor-free.The target initially has a finite exceptional vertex set whose deletion leaves a forest; the approach avoids needing a bound on that set's size.Source: §10.2 · p. 64
  • H is formed from the finite subgraph S and forest F by adding paths that connect their vertices.S contains U and shortest paths between pairs of vertices of U in the same component of G.Source: §10.2 · p. 65
  • The map ψ is a (1, f1.7(q))-quasi-isometry from G to H, where f1.7(q)=8f10.15(q)+4.The proof establishes both distance bounds with additive error f1.7(q).Source: §10.2 · pp. 65–67

11 Length and geodesic metric spaces

The results extend the paper’s fat-minor statements to length spaces and give a characterization for them; proper geodesic spaces satisfy an additional equivalence with being quasi-isometric to a tree. The proofs pass through quasi-isometric graph models.

11 Length and geodesic metric spaces

  • Every length space is quasi-isometric to a connected graph, and fat-minor exclusion transfers between quasi-isometric length spaces with fixed quasi-isometry constants.This yields length-space extensions of several theorems in the paper, including Theorem 1.10.Source: §11 · p. 67
  • For length spaces, being quasi-isometric to a graph with one vertex whose deletion leaves a tree is equivalent to excluding 2 · K3, or even ∞· K3, as a q-fat minor for some q > 0.Theorem 1.10 states these conditions are equivalent.Source: §11 · p. 67
  • For proper geodesic metric spaces, the length-space equivalences also include being quasi-isometric to a tree and excluding K3 as a q-fat minor for some q > 0.The proof reduces such spaces to locally finite graphs before contracting their cycles.Source: §11 · pp. 67–68

12 Discussion

The discussion proposes extensions of the paper’s coarse Erdős-Pósa and fat-minor results, including conjectures for forests, K2,3, planar graphs, and induced minors. It also records related known results, possible approaches, and an AI-use disclosure.

12 Discussion

  • The authors conjecture that graphs excluding a q-fat forest model are quasi-isometric to graphs excluding that forest as a minor, with an additive-distortion version proposed separately.They cite coarse path-width results as a possible starting point, while noting that subdivisions can introduce new forest minors.Source: §12 · pp. 68–69
  • The discussion asks whether planar graphs have the weak or full coarse Erdős-Pósa property, since planarity is necessary but not sufficient.It also presents conjectures for far-apart minor models and for induced minor models in planar graphs.Source: §12 · pp. 69–70
  • The paper conjectures that every forest has the coarse Erdős-Pósa property, extending the known weak version whose hitting-ball radius may depend on k.The authors believe that this dependence can be removed.Source: §12 · p. 69
  • For K2,3, the paper conjectures the coarse Erdős-Pósa property, noting that excluding a q-fat K2,3 model already implies quasi-isometry to cacti.Source: §12 · p. 69
  • A proposed route for planar-graph conjectures is to approximate graphs without the packing by quasi-isometric graphs of bounded tree-width, but a counterexample rules out the analogous strategy for fat-minor exclusion.The paper notes that the q = 2 case for far-apart models was recently proved with radius-1 balls.Source: §12 · p. 70

Statement of AI Use

  • The paper reports that ChatGPT 5.6 Sol and ChatGPT 6 Ultra were used only for minor edits to the final paper.Source: Statement of AI Use · p. 70

A Theorem 9.7 for infinite graphs

The section extends a forest packing-versus-hitting theorem to infinite settings under a finite-radius condition on components. It explains how the extension supports adapting a prior proof to infinite graphs while avoiding applications of finite results outside their scope.

A Theorem 9.7 for infinite graphs

  • The authors say they must inspect and slightly modify the prior proof to extend Theorem 9.7 to infinite graphs.Source: A Theorem 9.7 for infinite graphs · p. 75
  • The adaptation cautions that Simonovits’ theorem is used only on finite graphs, while the tree-decomposition technicality is avoided in the cycle-length-3 case.For forests, the relevant decomposition can be chosen with subtrees of radius at most 1.Source: A Theorem 9.7 for infinite graphs · pp. 75, 77
  • The finite forest theorem cannot simply be applied to infinite subgraphs: the section identifies one-way infinite paths with infinite subpaths as a counterexample.The infinite extension therefore retains a finite-radius condition on each component.Source: A Theorem 9.7 for infinite graphs · p. 76
  • For a forest and a family of non-null subgraphs with at most c components per member and finite-radius components, either k members are pairwise disjoint or at most 2c^2(k −1) vertices hit every member.Source: A Theorem 9.7 for infinite graphs · p. 76
  • The proof uses finite-family hitting sets and compactness to obtain a choice that works across the infinite family, then applies the two-set intersection property to select hitting vertices.Source: A Theorem 9.7 for infinite graphs · p. 76
Loading 2609.29414v1…