← All problems

The strong coarse Menger conjecture

Less than 1 year old · traced to

Let GG be a finite or infinite graph, and let X,Y⊆V(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. For sets S,T⊆V(G)S,T\subseteq V(G), let dist⁡G(S,T)\operatorname{dist}_G(S,T) be the infimum of the distances between their vertices. For S⊆V(G)S\subseteq V(G) and r∈Rr\in\mathbb R, let

NG≤r[S]={v∈V(G):dist⁡G(v,S)≤r}.N_G^{\leq r}[S]=\{v\in V(G):\operatorname{dist}_G(v,S)\leq r\}.

A set Z⊆V(G)Z\subseteq V(G) is (k,r)(k,r)-centered if Z⊆NG≤r[W]Z\subseteq N_G^{\leq r}[W] for some W⊆V(G)W\subseteq V(G) with ∣W∣≤k|W|\leq k. The strong coarse Menger conjecture. There exists a real number c>0c>0 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 a set (k−1,cr)(k-1,cr)-centered in GG intersecting all XX-YY paths. This is a large-scale analogue of Menger's theorem.

References

Status

  • Refuted: Tony Nguyen, Alex Scott, and Paul Seymour. A counterexample to the coarse Menger conjecture (Journal of Combinatorial Theory, Series B, 2025) https://arxiv.org/abs/2403.05630

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.