Asymptotic structure. VI. Distant paths across a disc
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915484514910208 |
|---|---|
| author | Nguyen, Tung Scott, Alex Seymour, Paul |
| author_facet | Nguyen, Tung Scott, Alex Seymour, Paul |
| contents | Menger's theorem says that, for $k\ge0$, if $S, T$ are sets of vertices in a graph $G$, then either there are $k + 1$ vertex-disjoint paths between $S$ and $T$, or there is a set X of at most $k$ vertices such that every $S$-$T$ path passes through $X$. The ``coarse Menger conjecture'' proposed a generalization of Menger's theorem for paths that are far apart: for all $k, c$ there exists $\ell$, such that for every graph $G$ and subsets $S, T \subset V (G)$, either there are $k + 1$ paths between $S$ and $T$, pairwise with distance more than $c$, or there is a set $X \subset V (G)$ of at most $k$ vertices such that every $S$-$T$ path has distance at most $\ell$ from $X$. This is known to be false, but may be true if $G$ is planar. Here we show that it is true if $G$ is planar and all vertices in $S \cup T$ are on the infinite region. In this case, we also obtain a linear-time algorithm to test for the existence of $k+ 1$ paths between $S$ and $T$, pairwise with distance more than $c$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_07174 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Asymptotic structure. VI. Distant paths across a disc Nguyen, Tung Scott, Alex Seymour, Paul Combinatorics 05C10, 05C12, 05C40 Menger's theorem says that, for $k\ge0$, if $S, T$ are sets of vertices in a graph $G$, then either there are $k + 1$ vertex-disjoint paths between $S$ and $T$, or there is a set X of at most $k$ vertices such that every $S$-$T$ path passes through $X$. The ``coarse Menger conjecture'' proposed a generalization of Menger's theorem for paths that are far apart: for all $k, c$ there exists $\ell$, such that for every graph $G$ and subsets $S, T \subset V (G)$, either there are $k + 1$ paths between $S$ and $T$, pairwise with distance more than $c$, or there is a set $X \subset V (G)$ of at most $k$ vertices such that every $S$-$T$ path has distance at most $\ell$ from $X$. This is known to be false, but may be true if $G$ is planar. Here we show that it is true if $G$ is planar and all vertices in $S \cup T$ are on the infinite region. In this case, we also obtain a linear-time algorithm to test for the existence of $k+ 1$ paths between $S$ and $T$, pairwise with distance more than $c$. |
| title | Asymptotic structure. VI. Distant paths across a disc |
| topic | Combinatorics 05C10, 05C12, 05C40 |
| url | https://arxiv.org/abs/2509.07174 |