arxiv: 2605.10068 · v1 · submitted 2026-05-11 · 🧮 math.CO · cs.DM· math.MG

Recognition: 3 theorem links

· Lean Theorem

Coarse Menger property of quasi-minor excluded graphs and length spaces

Chun-Hung Liu

Pith reviewed 2026-05-12 04:46 UTC · model grok-4.3

classification 🧮 math.CO cs.DMmath.MG

keywords coarse Menger propertygraph minorsminor-closed familiesMenger theoremquasi-isometrieslength spacespath packinglocally finite graphs

0 comments

The pith

Locally finite graphs excluding any fixed finite minor satisfy the weak coarse Menger property with f depending only on k and g linear in r.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that graphs which avoid a fixed finite graph as a minor obey a coarse form of Menger's theorem. For any two vertex sets in such a graph, one can always find either k paths that stay at least distance r apart or a collection of at most f balls that hit every path from one set to the other. The controlling functions can be chosen so the number of balls depends only on k while the ball radius grows linearly with r and stays independent of k. The same statement holds for any length space that is quasi-isometric to a graph of this kind, covering examples such as surfaces and certain infinite groups. A reader would care because the classical Menger theorem underpins many connectivity results, and this version supplies quantitative control in geometric and infinite settings.

Core claim

The set of locally finite graphs with an excluded finite minor has the weak coarse Menger property: there exist functions f and g such that for any such graph G, vertex subsets X and Y, and positive integers k and r, either there are k paths from X to Y that are pairwise at distance at least r, or there is a union of at most f(k,r) balls of radius at most g(k,r) that intersects every path from X to Y. Moreover f can be taken to depend only on k while g is linear in r and independent of k, and this dependence is optimal up to a constant factor. The statement extends to every length space that is quasi-isometric to a locally finite graph or metric graph with an excluded finite minor.

What carries the argument

The weak coarse Menger property, which equates the existence of k pairwise distance-r paths between two sets to the existence of a small cover of all paths by balls whose size is controlled by functions of k and r.

If this is right

The number of balls needed depends only on the number k of paths sought.
The radius of those balls grows linearly with the separation distance r and does not grow with k.
The same packing-or-blocking statement holds for any length space quasi-isometric to such a graph.
The result applies directly to complete Riemannian surfaces of finite Euler genus, string graphs, and Cayley graphs of finitely generated minor-excluded groups.
The linear dependence of the radius on r cannot be improved by more than a constant factor.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The controlled dependence on k and r may allow quantitative bounds on connectivity algorithms inside any minor-closed family.
The result suggests that forbidding a minor imposes strong uniform constraints on coarse-scale path structure even in infinite graphs.
Similar coarse versions of other classical packing theorems might hold inside the same graph classes.

Load-bearing premise

The graphs or spaces must be locally finite and must exclude some fixed finite graph as a minor.

What would settle it

A single locally finite graph that excludes a fixed finite minor yet requires either more than any function of k balls or balls whose radius grows faster than linearly in r to separate all paths at distance r would disprove the claim.

read the original abstract

Menger's theorem is an important building block of numerous results in the study of graph structure. We consider a variant in terms of coarse geometry. We say that a set of graphs has the weak coarse Menger property if there exist functions $f$ and $g$ such that for any graph $G$ in this set, subsets $X$ and $Y$ of vertices of $G$, and positive integers $k$ and $r$, either there exist $k$ paths between $X$ and $Y$ pairwise at distance at least $r$, or there exists a union of at most $f(k,r)$ balls of radius at most $g(k,r)$ intersecting all paths between $X$ and $Y$. Nguyen, Scott and Seymour proved that the set of all graphs does not have the weak coarse Menger property and asked whether every proper minor-closed family of finite graphs has it. In this paper, we provide a positive answer to this question in a stronger form: it is true for the set of locally finite graphs with an excluded finite minor, and the functions $f$ and $g$ can be chosen so that $f$ only depends on the number $k$ of the paths in the packing and the function $g$ is a linear function of the distance threshold $r$ and is independent of $k$, which is optimal up to a constant factor. Our result extends to every length space quasi-isometric to a locally finite graph or metric graph with an excluded finite minor, such as complete Riemannian surfaces of finite Euler genus, string graphs, and Cayley graphs of finitely generated minor-excluded groups.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

read the letter

This paper settles the Nguyen-Scott-Seymour question on the weak coarse Menger property for minor-closed families with stronger parameter bounds and extends the result to quasi-isometric length spaces. Liu shows that locally finite graphs excluding a fixed finite minor satisfy the property where f depends only on k and g is linear in r with no dependence on k. The abstract states this dependence is optimal up to a constant factor, which matches what grid examples suggest for planar graphs. The same conclusion carries over to length spaces quasi-isometric to such graphs, covering Riemannian surfaces of finite genus, string graphs, and Cayley graphs of minor-excluded groups. The argument uses the Robertson-Seymour structure theorem plus standard quasi-isometry comparisons. That combination is straightforward once the graph case is in hand, and the paper makes the functions' dependence explicit, which helps for later applications. The local finiteness assumption is necessary and clearly stated. The extension to length spaces requires checking that the quasi-isometry constants do not mess up the linear bound on g, but the outline gives no sign of trouble there. Readers in structural graph theory or geometric group theory will get the most from it, especially anyone who needs Menger-type statements with controlled parameters in metric settings. The work is grounded in established tools and resolves the open question without circularity or invented parameters. It deserves a serious referee because it improves on the asked-for result and opens the door to the listed applications. I would send it out for peer review.

Referee Report

0 major / 3 minor

Summary. The manuscript proves that locally finite graphs excluding a fixed finite minor satisfy the weak coarse Menger property: for any such graph G, vertex subsets X and Y, and positive integers k and r, either there exist k paths between X and Y that are pairwise at distance at least r, or there exists a union of at most f(k) balls of radius at most g(r) intersecting all X-Y paths, where f depends only on k and g is linear in r and independent of k. This bound is optimal up to a constant factor. The result extends to length spaces quasi-isometric to locally finite graphs or metric graphs with an excluded finite minor, including complete Riemannian surfaces of finite Euler genus, string graphs, and Cayley graphs of finitely generated minor-excluded groups. The proof relies on the Robertson-Seymour structure theorem together with quasi-isometry arguments.

Significance. If correct, the result gives a strong affirmative answer to the question of Nguyen, Scott, and Seymour on the weak coarse Menger property for proper minor-closed families of graphs, and does so with sharper dependence of the functions f and g than asked. The linearity of g in r together with its independence from k, and the extension to quasi-isometric length spaces, are notable strengths with direct implications for geometric group theory and topological graph theory. The paper correctly invokes the Robertson-Seymour theorem and quasi-isometry tools as the natural route from structural graph theory to the coarse setting.

minor comments (3)

[Introduction] §1 (Introduction): the precise citation to the Nguyen-Scott-Seymour question should include the arXiv number or full bibliographic details so that readers can locate the original formulation without ambiguity.
The title uses the term 'quasi-minor excluded'; the manuscript should clarify in the introduction or §2 whether this is synonymous with 'excluding a fixed finite minor' or denotes a strictly weaker notion, to avoid potential reader confusion.
[§3] Theorem statements in §3 and §4 would benefit from an explicit remark on whether the constants implicit in the linear function g depend on the excluded minor H; if they do, this should be stated for precision.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, accurate summary of the main theorem, and recommendation for minor revision. The report correctly identifies the key strengths, including the dependence of f only on k, the linearity of g in r independent of k, and the extensions to quasi-isometric length spaces. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper establishes a new theorem answering an open question of Nguyen-Scott-Seymour by proving the weak coarse Menger property for locally finite graphs excluding a fixed finite minor, with explicit f(k) and g(r) bounds derived from the Robertson-Seymour structure theorem combined with quasi-isometry arguments to length spaces. No step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation; the central claim is an independent existence result whose optimality is verified against external grid examples rather than presupposed. The extension to quasi-isometric length spaces follows directly from the graph case without circular renaming or imported uniqueness theorems.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard graph-theoretic and metric-space axioms with no free parameters or new entities introduced.

axioms (1)

standard math Standard axioms of graph theory, minor-closed families, and quasi-isometries of length spaces
Invoked throughout the statement and claimed extensions.

pith-pipeline@v0.9.0 · 5599 in / 1153 out tokens · 33859 ms · 2026-05-12T04:46:16.533284+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear
Theorem 1.4 ... either G contains k (ℓ,X,Y)-paths pairwise at distance ≥r, or there exists a set (f(k,r,ℓ), c_H r + ℓ)-centered in G intersecting all (ℓ,X,Y)-paths
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear
Lemma 3.1 ... or the set T ... is a tangle in L of order θ
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
use of Robertson-Seymour structure theorem for near-embeddings w.r.t. a tangle

Reference graph

Works this paper leans on

48 extracted references · 48 canonical work pages

[1]

Albrechtsen and J

S. Albrechtsen and J. Davies,Counterexample to the conjectured coarse grid theorem, arXiv:2508.15342

work page arXiv
[2]

Albrechtsen, M

S. Albrechtsen, M. Distel and A. Georgakopoulos,ExcludingK 2,t as a fat minor, arXiv:2510.14644

work page arXiv
[3]

Albrechtsen, R

S. Albrechtsen, R. W. Jacobs, P. Knappe and P. Wollan,A characterisation of graphs quasi-isometric toK 4-minor-free graphs, Combinatorica 45 (2025), article number 61

work page 2025
[4]

Albrechtsen, T

S. Albrechtsen, T. Huynh, R. W. Jacobs, P. Knappe and P. Wollan,A Menger-type theorem for two induced paths, SIAM J. Discrete Math. 38 (2024), 1438–1450

work page 2024
[5]

Blaˇ zej, M

V. Blaˇ zej, M. Pilipczuk and E. Protopapas,A coarse Menger’s theorem for planar and bounded genus graphs, in preparation

work page
[6]

Bonamy, N

M. Bonamy, N. Bousquet, L. Esperet, C. Groenland, C.-H. Liu, F. Pirot and A. Scott, Asymptotic dimension of minor-closed families and Assouad–Nagata dimension of sur- faces, J. Eur. Math. Soc. 26 (2024), 3739–3791

work page 2024
[7]

Bonamy, N

M. Bonamy, N. Bousquet, L. Esperet, C. Groenland, F. Pirot and A. Scott,Surfaces have (asymptotic) dimension 2, arXiv:2007.03582

work page arXiv 2007
[8]

Chepoi, F

V. Chepoi, F. F. Dragan, I. Newman, Y. Rabinovich and Y. Vax` es,Constant approxima- tion algorithms for embedding graph metrics into trees and outerplanar graphs, Discrete Comput. Geom. 47 (2012), 187–214

work page 2012
[9]

J. H. Conway and C. McA. Gordon,Knots and links in spatial graphs, J. Graph Theory 7 (1983), 445–453

work page 1983
[10]

Crouch and C.-H

J. Crouch and C.-H. Liu,Weak diameter choosability of graphs with an excluded minor, J. Combin. Theory Ser. B 174 (2025), 28–70

work page 2025
[11]

Davies,String graphs are quasi-isometric to planar graphs, arXiv:2510.19602

J. Davies,String graphs are quasi-isometric to planar graphs, arXiv:2510.19602

work page arXiv
[12]

Davies, M

J. Davies, M. Distel and R. Hickingbotham,Coarse structure for minor-free metrics, in preparation

work page
[13]

Distel,An alternative characterisation of graphs quasi-isometric to graphs of bounded treewidth, arXiv:2512.21946

M. Distel,An alternative characterisation of graphs quasi-isometric to graphs of bounded treewidth, arXiv:2512.21946

work page arXiv
[14]

Distel,Proper minor-closed classes of graphs have Assouad–Nagata dimension 2, Combin

M. Distel,Proper minor-closed classes of graphs have Assouad–Nagata dimension 2, Combin. Probab. Comput. 35 (2026), 1–25. 100

work page 2026
[15]

Distel, U

M. Distel, U. Giocanti, J. Hodor, C. Legrand-Duchesne and P. Micek,A coarse Gallai theorem, arXiv:2601.18439

work page arXiv
[16]

Dvoˇ r´ ak and R

Z. Dvoˇ r´ ak and R. Thomas,List-coloring apex-minor-free graphs, arXiv:1401.1399v2

work page arXiv
[17]

Fujiwara and P

K. Fujiwara and P. Papasoglu,A coarse-geometry characterization of cacti, arXiv:2305.08512

work page arXiv
[18]

Fujiwara and P

K. Fujiwara and P. Papasoglu,Asymptotic dimension of planes and planar graphs, Trans. Amer. Math. Soc. 374 (2021), 8887–8901

work page 2021
[19]

Gallai,Maximum-minimum s¨ atze und verallgemeinerte faktoren von graphen, Acta Math

T. Gallai,Maximum-minimum s¨ atze und verallgemeinerte faktoren von graphen, Acta Math. Acad. Sci. Hungar. 12 (1964), 131–173

work page 1964
[20]

Gartland, T

P. Gartland, T. Korhonen and D. Lokshtanov,On induced versions of Menger’s theorem on sparse graphs, arXiv:2309.08169

work page arXiv
[21]

Georgakopoulos and A

A. Georgakopoulos and A. Papasoglu,Graph minors and metric spaces, Combinatorica 45 (2025), article number 33

work page 2025
[22]

W. H. Gottschalk,Choice functions and Tychonoff’s theorem, Proc. Amer. Math. Soc. 2 (1951), 172

work page 1951
[23]

Gromov,Asymptotic invariants of infinite groups, in Geometric Group Theory, 1– 295, London Math

M. Gromov,Asymptotic invariants of infinite groups, in Geometric Group Theory, 1– 295, London Math. Soc. Lecture Note Ser. 182, Cambridge Univ. Press (1993)

work page 1993
[24]

Hendrey, S

K. Hendrey, S. Norin, R. Steiner and J. Turcotte,On an induced version of Menger’s theorem, Electron. J. Combin. 31 (2024), #P4.28

work page 2024
[25]

Hickingbotham

R. Hickingbotham,Graphs that are quasi-isometric to graphs with bounded treewidth, arXiv:2501.10840

work page arXiv
[26]

Hickingbotham and G

R. Hickingbotham and G. Joret,An inducedA-path theorem, arXiv:2512.17232

work page arXiv
[27]

Huynh,The linkage problem for group-labelled graphs, Ph

T. Huynh,The linkage problem for group-labelled graphs, Ph. D Thesis, University of Waterloo, 2009

work page 2009
[28]

Jørgensen and U

M. Jørgensen and U. Lang,Geodesic spaces of low Nagata dimension, Ann. Fenn. Math. 47 (2022), 83–88

work page 2022
[29]

Juvan, A

M. Juvan, A. Malniˇ c and B. Mohar,Systems of curves on surfaces, J. Combin. Theory Ser. B 68 (1996), 7–22

work page 1996
[30]

Liu,Assouad–Nagata dimension of minor-closed metrics, Proc

C.-H. Liu,Assouad–Nagata dimension of minor-closed metrics, Proc. London Math. Soc. 130 (2025), e70032

work page 2025
[31]

Liu,Asymptotic dimension of minor-closed families and beyond, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), (2021), 1997–2013

C.-H. Liu,Asymptotic dimension of minor-closed families and beyond, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), (2021), 1997–2013

work page 2021
[32]

Liu,Packing topological minors half-integrally, J

C.-H. Liu,Packing topological minors half-integrally, J. London Math. Soc. 106 (2022), 2193–2267. 101

work page 2022
[33]

Liu and R

C.-H. Liu and R. Thomas,Excluding subdivision of bounded degree graphs, J. Combin. Theory, Ser. B 134 (2019), 1–35

work page 2019
[34]

Nguyen, A

T. Nguyen, A. Scott and P. Seymour,A counterexample to the coarse Menger conjecture, J. Combin. Theory Ser. B 173 (2025), 68–82

work page 2025
[35]

Nguyen, A

T. Nguyen, A. Scott and P. Seymour,Asymptotic structure. I. Coarse tree-width, arXiv:2501.09839

work page arXiv
[36]

Nguyen, A

T. Nguyen, A. Scott and P. Seymour,Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture, arXiv:2508.14332

work page arXiv
[37]

Nguyen, A

T. Nguyen, A. Scott and P. Seymour,Asymptotic structure. V. The coarse Menger conjecture in bounded path-width, arXiv:2509.08762

work page arXiv
[38]

Nguyen, A

T. Nguyen, A. Scott and P. Seymour,Asymptotic structure. VI. Distant paths across a disc, arXiv:2509.07174

work page arXiv
[39]

Robertson and P

N. Robertson and P. D. Seymour,Graph minors. V. Excluding a planar graph, J. Com- bin. Theory, Ser. B 41 (1986), 92–114

work page 1986
[40]

Robertson and P

N. Robertson and P. D. Seymour,Graph minors. IX. Disjoint crossed paths, J. Combin. Theory, Ser. B 49 (1990), 40–77

work page 1990
[41]

Robertson and P

N. Robertson and P. D. Seymour,Graph minors. X. Obstructions to tree-decomposition, J. Combin. Theory, Ser. B 52 (1991), 153–190

work page 1991
[42]

Robertson and P

N. Robertson and P. D. Seymour,Graph minors. XI. Circuits on a surface, J. Combin. Theory, Ser. B 60 (1994), 72–106

work page 1994
[43]

Robertson and P

N. Robertson and P. D. Seymour,Graph minors. XII. Distance on a surface, J. Combin. Theory, Ser. B 64 (1995), 240–272

work page 1995
[44]

Robertson and P

N. Robertson and P. D. Seymour,Graph minors. XIV. Extending an embedding, J. Combin. Theory, Ser. B 65 (1995) 23–50

work page 1995
[45]

Robertson and P

N. Robertson and P. D. Seymour,Graph minors. XVI. Excluding a non-planar graph, J. Combin. Theory, Ser. B 89 (2003), 43–76

work page 2003
[46]

Robertson, P

N. Robertson, P. Seymour and R. Thomas,Quickly excluding a planar graph, J. Combin. Theory, Ser. B 62 (1994), 323–348

work page 1994
[47]

Sachs,On spatial representation of finite graphs, Proceedings of a conference held in Lag´ ow, Poland, February 10–13, 1981, Lecture Notes in Mathematics, Vol

H. Sachs,On spatial representation of finite graphs, Proceedings of a conference held in Lag´ ow, Poland, February 10–13, 1981, Lecture Notes in Mathematics, Vol. 1018, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1983

work page 1981
[48]

Yu,The Novikov conjecture for groups with finite asymptotic dimension, Ann

G. Yu,The Novikov conjecture for groups with finite asymptotic dimension, Ann. of Math. 147 (1998), 325–355. 102

work page 1998