Nguyen–Scott–Seymour's weak coarse Menger conjecture

From papers

Let GG be a finite or infinite graph, and let X,YV(G)X,Y\subseteq V(G). An XX-YY path is a path with at least one end in XX and at least one end in YY. A set ZV(G)Z\subseteq V(G) is (a,b)(a,b)-centered if it is contained in the union of at most aa balls of radius at most bb. Nguyen–Scott–Seymour's weak coarse Menger conjecture. There exist functions f,g:NRf,g:\mathbb N\rightarrow\mathbb R such that for any graph GG, subsets X,YX,Y of V(G)V(G) and positive integers k,rk,r, either GG contains kk XX-YY paths pairwise at distance at least rr, or there exists an (f(k,r),g(k,r))(f(k,r),g(k,r))-centered set intersecting all XX-YY paths. The conjecture is a weakening of the strong coarse Menger conjecture, allowing both the number and radius of covering balls to depend on kk and rr. Nguyen, Scott and Seymour later disproved it as well.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Chun-Hung Liu, “Coarse Menger property of quasi-minor excluded graphs and length spaces”, arXiv:2605.10068 (2026).

Solutions 0

No solutions have been posted yet.