Coarse Menger for surface-embedded graphs

Conjecture 1.2 (Coarse Menger conjecture for surfaces) · arXiv:2509.07174

arXiv Conjecture high confidence— first stated 2025-09-08

Authors: Tung Nguyen, Alex Scott, Paul Seymour

Status partial high confidence

Conjecture 1.2 (the strong Coarse Menger conjecture for surfaces) remains open but has partial progress. Blažej, Pilipczuk, and Protopapas (arXiv:2605.11112, 2026) prove the weak form for graphs embeddable on any fixed surface: if fewer than k pairwise d-apart S-T paths exist, then there is a vertex set X with |X| ≤ f(k,d) such that every S-T path is within distance d of some vertex of X. This weak form allows |X| to grow with d, whereas Conjecture 1.2 requires the stronger bound |X| ≤ k independent of the distance parameter; the full conjecture remains open.

Cited literature (1)

partial A coarse Menger's Theorem for planar and bounded genus graphs (2026)

Václav Blažej, Michał Pilipczuk, Evangelos Protopapas · arXiv preprint · arXiv:2605.11112

Proves the weak Coarse Menger conjecture for graphs embeddable on any fixed surface (Theorem 1.1): if fewer than k pairwise d-apart S-T paths exist, then there is a vertex set X with |X| ≤ f(k,d) such that every S-T path lies within distance d of X; the stronger bound |X| ≤ k required by Conjecture 1.2 is not established.

Reviewer notes. The weak Coarse Menger conjecture for surfaces is settled by arXiv:2605.11112 (2026), which cites Nguyen–Scott–Seymour's counterexample paper (part IV) but not part VI (2509.07174), likely because 2605.11112 was largely written before part VI appeared. The strong form of Conjecture 1.2 (∣X∣ ≤ k with ℓ depending only on k and c) remains open. The internal reference 2412.13893 is a fuzz-match false positive.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Conjecture. Let $\mathcal{S}$ be a fixed surface. For all integers $k,c\geq 0$ there exists $\ell>0$ with the following property. Let $G$ be a graph that embeds on $\mathcal{S}$ and let $S,T\subseteq V(G)$. Then either $\bullet$ there are $k+1$ paths between $S,T$, pairwise $c$-distant; or $\bullet$ there is a set $X\subseteq V(G)$ with $|X|\leq k$ such that every path between $S,T$ contains a vertex with distance at most $\ell$ from some member of $X$.

Context

The original Coarse Menger conjecture (attributed to Albrechtsen, Huynh, Jacobs, Knappe and Wollan, and independently to Georgakopoulos and Papasoglu) was shown to be false for general graphs by the same authors (Nguyen–Scott–Seymour) in [11], with counterexamples that are highly non-planar (unbounded genus). Since the counterexamples rely on non-planarity, the authors propose that a surface-restricted version may still hold.

Notes. The paper proves a special case (Theorem 1.3): the conjecture holds when $G$ is planar and all vertices of $S\cup T$ lie on the infinite region, with the blocking structure being at most $k$ connected subgraphs whose diameters sum to at most $200k^3c$.

Source paper

Asymptotic structure. VI. Distant paths across a disc
Tung Nguyen, Alex Scott, Paul Seymour · 2025-09-08
https://arxiv.org/abs/2509.07174