Line-width and path-width
Tung Nguyen, Alex Scott, Paul Seymour · 2025
Read Line-width and 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-16786.txt.
Introduction
Tung Nguyen, Alex Scott, and Paul Seymour refine a width measure for endless graphs in a 2025 math paper. Path-width sums up how tree-like a finite graph is. Extending it to infinite graphs in the obvious way breaks down. A nicer extension indexes the parts by any total order, giving line-decompositions and line-width.
The team ask whether the order can always be a well-order, which is easier to use. They show a graph with line-width at most k has such a decomposition with width at most twice k. That bound is the best possible. The result tidies a tool used in graph structure theory.
Catalog record
| CREATOR | Tung Nguyen, Alex Scott, Paul Seymour |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-16786
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Line-width and path-width Tung Nguyen, Alex Scott, Paul Seymour Abstract For finite graphs, path-width is an interesting and useful concept, but if we extend it to infinite graphs in the most obvious way (by making the indexing path infinite), it does not work nicely. The simplest extension that works nicely is to allow the indexing set to be any totally-ordered set, and then the corresponding decomposition is called a “line-decomposition”, and the maximum bag size needed is called “line-width”. In particular, the indexing set need not be a well-order; but the corresponding decomposition would be easier to use if it was. We show that if a graph has line-width at most k k , it admits a well-ordered line-decomposition with width at most 2 k 2k , and this is best possible. 1 Introduction A tree-decomposition of a finite graph G is a pair (T,(W_{t}:t\in V(T))) , where T is a finite tree, and W_{t} is a subset of V(G) for each t\in V(T) (called a bag ), such that: • G=\bigcup_{t\in V(T)}G[W_{t}] , and • for all t_{1},t_{2},t_{3}\in V(T) , if t_{2} lies on the path of T between t_{1},t_{3} , then B_{t_{1}}\cap B_{t_{3}}\subseteq B_{t_{2}} . The width of a tree-decomposition (T,(W_{t}:t\in V(T))) is the maximum of the numbers |W_{t}|-1 for t\in V(T) , and the tree-width of G is the minimum width of a tree-decomposition of G . Similarly, a path-decomposition of a finite graph G is the same except that we require T to be a path; and the path-width of a finite graph is the minimum width of a path-decomposition. We extend tree-width and path-width to infinite graphs by allowing the indexing tree or path to be infinite (thus, for a path-decomposition, the indexing path might be finite, or one-way infinite, or two-way infinite). This seems the most natural extension, and for tree-width it works nicely. In particular, there is a “compactness” theorem of Thomas [ 6 ] (and see also [ 1 ] for a proof): 1.1 A graph G has tree-width at most k if and only if every finite subgraph of G has tree-width at most k . There are several ways to define infinite analogues of finite trees: for instance, topological trees, or set-theoretic trees. We could choose our favourite one of these definitions (let us call them “supertrees”), and use a supertree as the indexing set, giving “supertree-decompositions” and “supertree-width”. But this gives nothing new: any graph with supertree-width at most k also has tree-width at most k . To see this, observe that, whatever definition of supertree we have taken, if G has supertree-width at most k , then all its finite subgraphs have tree-width at most k , and therefore G has tree-width at most k by Thomas’ theorem 1.1 . For path-width, the analogue of Thomas’ theorem is far from true. For instance, all graphs with finite path-width have only countably many vertices, so a graph with uncountably many vertices and no edges is already a counterexample; all its finite subgraphs have path-width zero, and yet G does not have finite path-width. Even for countable graphs, the analogue is still not true: for instance, any graph with infinitely many infinite connected subgraphs that are pairwise vertex-disjoint does not have finite path-width, and yet its finite subgraphs could all have very small path-width. Thus, for an infinite graph G , all finite subgraphs having path-width at most k does not imply that G has path-width at most k . But what structure of G does it imply? This was answered in [ 1 ] as follows. A line is a nonempty set L together with a linear order \leq_{L} . A line-decomposition of G is a pair (L,(W_{t}:t\in L)) where L is a line, and each W_{i} is a subset of V(G) , satisfying: • G=\bigcup_{t\in L}G[W_{t}] , and • W_{t}\cap W_{t^{\prime\prime}}\subseteq W_{t^{\prime}} for all t,t^{\prime},t^{\prime\prime}\in L with t\leq_{L}t^{\prime}\leq_{L}t^{\prime\prime} . The second condition here is called the “betweenness axiom”. We define the width of such a decomposition to be the maximum of |B_{t}|-1 over all t\in L , if this maximum exists, and \infty otherwise; and the line-width of G is the minimum width of a line-decomposition. (This definition was used in [ 4 , 5 ] , to increase the generality of some results about graphs with bounded path-width. It is also used in [ 2 , 3 ] , where what we call “line-decompositions” are called “linear decompositions”.) With Chudnovsky, we proved in [ 1 ] that: 1.2 A graph G has line-width at most k if and only if every finite subgraph of G has path-width at most k . But do we need such general linear orders? Could we restrict the order-type somehow, perhaps in terms of the maximum bag-size? Could we make the order a well-order? This paper is an investigation into these and related questions. In particular, we will show that: 1.3 If a graph G has finite line-width k , then it admits a line-decomposition (L,(W_{t}:t\in L)) of width at most 2k such that L is a well-order. We will also show that 2k is best possible. At the end of the paper, we look at a different question. We will show that, after a little tidying, every line-decomposition of width \leq k of a graph G can be built by substitution and concatenation, starting from so-called “prime” line-decompositions, which are much simpler. 2 Tidying a line-decomposition If L is a line, an interval of L is a nonempty subset I\subseteq L such that if r,s,t\in L with r\leq_{L}s\leq_{L}t , and r,t\in I , then s\in I . An interval I is initial if I\neq L and for all s,t\in L with s\leq_{L}t , if t\in I then s\in I . (Note that if I is an initial interval then I,L\setminus I are both nonempty, and so L\setminus I is an initial interval of the line obtained from L by reversing its order.) If (L,(W_{t}:t\in L)) is a line-decomposition of G , and I is an interval, we define W(I)=\bigcup_{t\in I}W_{t}. If I is an initial interval, then W(I)\cap W(L\setminus I) is called the I -split ; every path between W(I),W(L\setminus I) has a vertex in this set. We say X is a split if X is the I -split for some initial interval I . Let us see first some easy things we can do to make a line-decomposition nicer without increasing its width. Let (L,(W_{t}:t\in L)) be a line-decomposition of G , of finite width. If there are distinct s,s^{\prime}\in L with W_{s}=W_{s^{\prime}} , we could remove one of s,s^{\prime} from L and still have a line-decomposition. In general, we can partition L into equivalence classes under the relation s\equiv s^{\prime} if W_{s}=W_{s^{\prime}} , and choose one element of each equivalence class. Let L^{\prime} be the set of chosen elements, ordered by the order inherited from L . Then (L^{\prime},(W_{t}:t\in L^{\prime})) is still a line-decomposition of G , with the same width, and now there are no repeated bags. So we could assume that all the sets W_{t}\;(t\in L) are distinct. Now let L^{\prime} be the set of all s\in L such that there is no s^{\prime}\in L with