Coarse Menger separation with distance 2

Open case: Coarse Menger Conjecture for c=2 · arXiv:2508.14332

arXiv Informal medium confidence— first stated 2025-08-20

Authors: Tung Nguyen, Alex Scott, Paul Seymour

Status partial high confidence

The Coarse Menger Conjecture for c=2 was explicitly left open in the source paper, which disproves the weak coarse Menger conjecture for c≥3. Subsequent work (arXiv:2509.08762) proves the coarse Menger conjecture for all graphs of bounded path-width, giving a partial positive result that applies to c=2 in that restricted class. A further paper (arXiv:2605.11112) establishes a coarse Menger theorem for planar and bounded-genus graphs. The c=2 case for general graphs remains open.

Cited literature (2)

partial Asymptotic structure. V. The coarse Menger conjecture in bounded path-width (2025)

Tung Nguyen, Alex Scott, Paul Seymour · arXiv preprint · arXiv:2509.08762

Proves the coarse Menger conjecture for all graphs of bounded path-width (across all values of c), providing a partial positive result for the c=2 open case in this restricted graph class.
partial A coarse Menger's Theorem for planar and bounded genus graphs (2026)

unconfirmed · arXiv preprint · arXiv:2605.11112

Proves a coarse version of Menger's theorem for planar and bounded-genus graphs, giving partial progress on the coarse Menger conjecture (including the c=2 case) for those surface-embeddable graph families.

Reviewer notes. The c=2 case of the Coarse Menger Conjecture remains open for general graphs. The source paper's main contribution is a counterexample for c≥3. Partial results exist for bounded path-width (arXiv:2509.08762) and planar/bounded-genus graphs (arXiv:2605.11112). The internal reference arXiv:2412.13893 is a false match and does not concern this conjecture.

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

Informal. It is unknown whether Conjecture 1.1 holds when $c = 2$: for all integers $k \geq 1$ there exists $\ell > 0$ such that for every graph $G$ and $S, T \subseteq V(G)$, either there are $k$ paths between $S, T$ pairwise at distance at least $2$, or there is a set $X \subseteq V(G)$ with $|X| \leq k-1$ such that every $S$-$T$ path contains a vertex within distance $\ell$ of some member of $X$.

Context

The authors note that the case $c = 3$ is of special interest because a positive result for $c = 3$ would imply one for all $c \geq 3$ (via taking the $c$-th power of $G$). They explicitly remark that 'the conjecture remains open when $c = 2$, and we have nothing to say about that case in this paper.'

Notes. Stated as a passing remark in the introduction; no formal conjecture label. Refers specifically to the strong-form Conjecture 1.1 restricted to c=2.

Source paper

Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture
Tung Nguyen, Alex Scott, Paul Seymour · 2025-08-20
https://arxiv.org/abs/2508.14332