Graphs with cycle spaces generated by bounded-length cycles have the coarse Menger property, with corollaries for hyperbolic graphs, finitely presented groups, and planar graphs with bounded faces.
Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
abstract
Coarse graph theory concerns finding 'coarse' analogues of graph theory theorems, replacing disjointness with being far apart. One of the most interesting open questions is to find a coarse analogue of Menger's theorem, which characterizes when there are $k$ vertex-disjoint paths between two given sets $S,T$ of vertices of a graph. We showed in an earlier paper that the most natural such analogue is false, but a weaker statement remained as a popular open question. Here we show that the weaker statement is also false. More exactly, suppose that $S,T$ are sets of vertices of a graph $G$, and there do not exist $k$ paths between $S,T$, pairwise at distance at least $c$. To make an analogue of Menger's theorem, one would like to prove that there must be a small set $X\subseteq V(G)$ such that every $S-T$ path of $G$ passes close to a member of $X$: but how small and how close? In view of Menger's theorem, one would hope for $|X|<k$ and 'close' some function of $k,c$ (and indeed, this was conjectured by Georgakopoulos and Papasoglu, and independently, by Albrechtsen, Huynh, Jacobs, Knappe and Wollan); but we showed that this is false, even if $c=3$ and $k=3$. Here we upgrade the counterexample: we show that, even if $c=k=3$, no pair of constants (for 'small' and 'close') work. For all $\ell, m$, there is a graph $G$ and $S,T\subseteq V(G)$, such that there do not exist three $S-T$ paths pairwise with distance at least three, and yet there is no $X$ with $|X|\le m$ such that every $S-T$ path passes within distance at most $\ell$ of $X$.
citation-role summary
background 1
contradiction 1
citation-polarity summary
fields
math.CO 5years
2026 5representative citing papers
In planar and bounded-genus graphs, absence of k pairwise d-far S-T paths implies a vertex set of size f(d,k) whose d-neighborhood intersects every S-T path.
Locally finite graphs with an excluded finite minor have the weak coarse Menger property with f depending only on k and g linear in r independent of k.
Every graph admits a tree decomposition with small-diameter adhesion sets where same-bag vertices cannot be separated by small, distant vertex sets.
Every connected graph has a tree-decomposition with bounded-diameter adhesion sets and coarsely inseparable bags, yielding a metric analogue of the block-cutvertex tree.
citing papers explorer
-
A coarse Menger theorem for hyperbolic graphs, finitely presented groups, and more
Graphs with cycle spaces generated by bounded-length cycles have the coarse Menger property, with corollaries for hyperbolic graphs, finitely presented groups, and planar graphs with bounded faces.
-
A coarse Menger's Theorem for planar and bounded genus graphs
In planar and bounded-genus graphs, absence of k pairwise d-far S-T paths implies a vertex set of size f(d,k) whose d-neighborhood intersects every S-T path.
-
Coarse Menger property of quasi-minor excluded graphs and length spaces
Locally finite graphs with an excluded finite minor have the weak coarse Menger property with f depending only on k and g linear in r independent of k.
-
A coarse block-cut tree theorem
Every graph admits a tree decomposition with small-diameter adhesion sets where same-bag vertices cannot be separated by small, distant vertex sets.
-
A coarse block-cutvertex tree-decomposition
Every connected graph has a tree-decomposition with bounded-diameter adhesion sets and coarsely inseparable bags, yielding a metric analogue of the block-cutvertex tree.