Asymptotic structure. V. The coarse Menger conjecture in bounded path-width
Tung Nguyen, Alex Scott, Paul Seymour · 2025
Read Asymptotic structure. V. The coarse Menger conjecture in bounded path-width by Tung Nguyen, Alex Scott, Paul Seymour (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-08762.txt.
Introduction
Alex Divoux and 3 co-authors prove a coarse version of Menger's theorem for graphs with bounded path-width in a 2025 paper. Menger's theorem links disjoint paths between two sets with small separating sets. The coarse version asks for paths that stay far apart.
Earlier work showed the claim is false in general, using graphs with large tree-like parts. Here, if a certain planar graph is excluded as a minor, the coarse claim holds for all graphs. That includes graphs of bounded path-width and series-parallel graphs. The path-width case is surprising, since the claim fails for bounded tree-width. The paper is part five of a series.
Catalog record
| CREATOR | Tung Nguyen, Alex Scott, Paul Seymour |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-08762
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Asymptotic structure. V. The coarse Menger conjecture in bounded path-width Tung Nguyen, Alex Scott, Paul Seymour Abstract Menger’s theorem tells us that if S , T S,T are sets of vertices in a graph G G , then (for k ≥ 0 k\geq 0 ) either there are k + 1 k+1 vertex-disjoint paths between S S and T T , or there is a set of k k vertices separating S S and T T . But what if we want the paths to be far apart, say at distance at least c c ? One might hope that we can find either k + 1 k+1 paths pairwise far apart, or k k sets of bounded radius that separate S S and T T , where the bound on the radius is some ℓ \ell that depends only on k , c k,c (the “coarse Menger conjecture”). We showed in an earlier paper that this is false for all k ≥ 2 k\geq 2 and c ≥ 3 c\geq 3 . To do so we gave a sequence of finite graphs, counterexamples for larger and larger values of ℓ \ell with k = 2 k=2 , c = 3 c=3 . Our counterexamples contained subdivisions of uniform binary trees with arbitrarily large depth as subgraphs. Here we show that for any binary tree T T , the coarse Menger conjecture is true for all graphs that contain no subdivision of T T as a subgraph, that is, it is true for graphs with bounded path-width (and, further, for graphs with bounded coarse path-width). This is perhaps surprising, since it is false for bounded tree-width. 1 Introduction Let S,T be sets of vertices of a graph G . (In this paper, all graphs are finite and have no loops or multiple edges.) Menger’s theorem [ 7 ] tells us that either there are k+1 pairwise vertex-disjoint paths between S and T , or there is a set X of at most k vertices such that every S - T path in G meets X . But what if we want the paths to be pairwise far apart? In this case, the question is much harder. Bienstock [ 3 ] showed that it is NP-hard to decide whether, given four vertices s_{1},s_{2},t_{1},t_{2} of a graph G , there are two paths between between \{s_{1},s_{2}\} and \{t_{1},t_{2}\} that have distance \geq 2 , that is, they are vertex-disjoint and there is no edge joining them. This was recently extended by Baligács and MacManus [ 2 ] , who showed the same thing for distance \geq c , for each c\geq 3 . Since the problem is NP-complete, one would not expect to find a necessary and sufficient condition for the existence of k+1 S - T paths at distance at least c ; but still one could hope for some sort of obstruction that is necessary for excluding k+1 S - T paths at distance at least c , and sufficient for excluding k+1 S - T ps at distance more than some larger number depending on k,c . Two groups of researchers, Albrechtsen, Huynh, Jacobs, Knappe and Wollan [ 1 ] , and independently Georgakopoulos and Papasoglu [ 5 ] , proposed such a statement: 1.1 Coarse Menger Conjecture: For all integers k\geq 0 and c\geq 1 there exists \ell\geq 0 with the following property. Let G be a graph and let S,T\subseteq V(G) . Then either • there are k+1 paths between S,T , pairwise at distance at least c ; or • 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 . Both groups showed that this is true for k=1 , and Gartland, Korhonen and Lokshtanov [ 4 ] and Hendrey, Norin, Steiner, and Turcotte [ 6 ] proved it for bounded degree graphs when c=2 . However, we showed in [ 8 ] that the coarse Menger conjecture is false for all k\geq 2 , for any fixed c\geq 3 . Indeed, it remains false even if we weaken the bound |X|\leq k in the second bullet to |X|\leq m , where m is any constant depending on k,c [ 12 ] . Thus, we need to lower our sights a little, and one way to do so is to work in restricted classes of graphs. The counterexamples of [ 8 ] have unbounded genus, and contain (as subgraphs) uniform binary trees of arbitrary depth, and therefore they have unbounded “path-width” (defined in the next section). It might be true that the coarse Menger conjecture holds for graphs of bounded genus, but this is open; see [ 13 ] for some progress in this direction. Here we prove that the coarse Menger conjecture is true for graphs of bounded path-width. More exactly, we will prove: 1.2 Let k,d\geq 0 and c\geq 1 be integers. Then there exists \ell\geq 0 , such that for every graph G with path-width at most d , and all S,T\subseteq V(G) , either: • there are k+1 paths between S,T , pairwise at distance at least c ; or • 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 . Thus the coarse Menger conjecture is true for graphs of bounded path-width, and we will deduce in the conclusion that it also holds for graphs of “bounded coarse path-width”. Curiously, the coarse Menger conjecture is not true for graphs of bounded tree-width, since the counterexamples of [ 8 ] have tree-width six. 2 Subdivisions and path-width The uniform binary tree of depth d\geq 2 is the tree H such that for some r\in V(H) , r has degree two, all other vertices have degree one or three, and every vertex of degree one has distance exactly d-1 from r . Thus, H has 2^{d}-1 vertices. We denote this tree by H_{d} . If H is a graph, a subdivision of H is a graph obtained from H by replacing each of its edges by a path of length at least one joining the same pair of vertices, where these paths are pairwise vertex-disjoint except for their ends. For n\geq 0 , let us say an n -subdivision of H is a subdivision obtained by replacing each edge by a path of length \leq n (and at least one). (This is inconsistent with the standard term “1-subdivision”, which means replacing each edge with a path of length two, but convenient for us.) Let us define path-width. A graph G has path-width at most d if and only if there is a sequence W_{1},\ldots,W_{n} of subsets of its vertex set, satisfying: • |W_{i}|\leq d+1 for 1\leq i\leq n ; • G[W_{1}]\cup\cdots\cup G[W_{n}]=G ; and • W_{i}\cap W_{k}\subseteq W_{j} for 1\leq i\leq j\leq k\leq n . We do not really need this definition. The only thing about bounded path-width that concerns us is a theorem of Robertson and Seymour [ 14 ] : 2.1 For every integer d\geq 2 , there exists k , such that