Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913998191984640 |
|---|---|
| author | Nguyen, Tung Scott, Alex Seymour, Paul |
| author_facet | Nguyen, Tung Scott, Alex Seymour, Paul |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_14332 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture Nguyen, Tung Scott, Alex Seymour, Paul Combinatorics 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$. |
| title | Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2508.14332 |