Source-linked AI summary
Countable Graphs with Finite Path-width: Characterisation and Universality
Tony Huynh, Freddie Illingworth, Nikolai Karol, Florian Lehner, Chun-Hung Liu, János Pach, David R. Wood
TL;DR
The paper studies finite path-width and universality for graphs with bounded path-width or line-width. It develops well-order-width tools and proves both universal constructions and lower bounds under the subgraph relation.
Problem
Finite path-width is difficult to characterize in countably infinite graphs, and universality for bounded path-width differs from the corresponding tree-width setting.
Method
The paper introduces well-order-decompositions and well-order-width to analyze line-decompositions and construct universal graphs.
Results
A universal graph exists for L_k with line-width at most 4k^2 + 6k, while every universal graph for P_k, k ≥ 2, has line-width at least k + 1; no finite-path-width graph is universal for locally finite P_1.
Takeaways & Limitations
Universality for bounded path-width is subtler than for bounded tree-width, whereas bounded line-width admits universal graphs with a quadratic line-width bound.
Takeaways & Limitations
The lower-bound theorem requires k ≥ 2, because a graph of line-width 1 is universal for L_1.
Abstract
from arXiv · showhide
We study path-width and the closely related parameter line-width in countably infinite graphs. Our first result characterises the graphs of finite path-width: they are the graphs that do not have infinitely many vertices of infinite degree, do not have infinitely many pairwise disjoint infinite paths, and contain no subdivision of some finite tree of maximum degree 3. We then investigate universality under the subgraph relation for graphs of bounded path-width or line-width. In particular, we prove that there exists a universal graph with line-width $\mathcal{O}(k^2)$ for the class of graphs with line-width at most $k$. In contrast, we show that no graph of finite path-width is universal for the class of locally finite graphs with path-width $1$. Finally, we show that for each $k\geq 2$, every universal graph for the class of graphs with path-width at most $k$ has line-width at least $k + 1$.
1 Introduction
The paper studies finite path-width in countable infinite graphs and universality for bounded path-width and line-width. It characterises finite path-width and establishes contrasting upper and lower bounds for universal graphs.
- Path-width: Path-width is defined through path-decompositions indexed by N, with width determined by the largest bag size minus one.The decomposition covers all vertices, contains both endpoints of every edge in a bag, and requires each vertex’s bags to be consecutive.
- Characterisation: Theorem 1 shows that finitely many infinite-degree vertices, finitely many disjoint one-way infinite paths, and bounded finite-subgraph path-width suffice for finite path-width.These conditions are stated with bounds d, c, and k, and imply the excluded-subgraph characterisation.
- Characterisation: Finite path-width is equivalent to having finitely many infinite-degree vertices, finitely many pairwise disjoint one-way infinite paths, and no subdivision of some finite maximum-degree-3 tree.This is the paper’s excluded-subgraph characterisation.
- Related width parameters: Line-width generalises path-width by allowing bags to be indexed by any total order, and every graph satisfies lw(G) <= pw(G), with equality for finite graphs.Line-width also has a compactness theorem: it is at most c exactly when every finite subgraph has path-width at most c.
- Universality: No finite-path-width graph is universal for locally finite graphs of path-width 1; every universal graph for that class has path-width ∞.More generally, a universal graph for Pk is not itself in Pk, and for k = 1 its path-width must be infinite.
2 Path-width, Line-width and Well-order-width
The paper introduces well-order-width to make line-decompositions easier to handle and relates it to line-width through componentwise and factor-two bounds.
- Well-order-width: Well-order-width restricts line-decompositions to totally ordered index sets that are well-ordered, and Wk denotes graphs with well-order-width at most k.A well-order has a least element in every non-empty subset and admits no infinite strictly descending sequence.
- Relationship between parameters: Line-width and well-order-width are within a factor of 2, enabling universal constructions for line-width classes to proceed through well-order-width.The paper explicitly applies this relationship in the proof of Theorem 5.
- Component structure: The well-order-width of a graph equals the supremum of the well-order-widths of its connected components.The proof concatenates well-order-decompositions of the components without increasing the maximum width.
- Construction: For infinitely many components, concatenating their well-order index orders still produces a well-order decomposition whose width is the maximum component width.The construction uses pairwise disjoint index sets and orders all indices of earlier components before later ones.
- Component structure: The line-width of a graph likewise equals the supremum of the line-widths of its connected components.This gives a parallel componentwise decomposition property for line-width.
3 Graphs with Infinite Path-width
This section proves that infinitely many disjoint infinite paths or infinitely many infinite-degree vertices force infinite path-width, and applies the latter to universality.
- Infinite paths: k pairwise disjoint 1-way infinite paths force pw(G) ≥ k.Infinitely many such paths therefore imply infinite path-width.
- Infinite paths: The bound pw(G) ≥ k is tight for the disjoint union of k 1-way infinite paths.A width-k path-decomposition uses bags containing edge endpoints on one path and one vertex from every other path.
- Infinite degree: k vertices of infinite degree force pw(G) ≥ k.Infinitely many vertices of infinite degree consequently imply pw(G) = ∞.
- Infinite degree: The bound for k infinite-degree vertices is tight because Kk,ℵ0 has path-width k.This establishes exactness for the stated family.
- Universality: No graph of finite path-width is universal for locally finite graphs with path-width 1.Such a universal graph would have infinite path-width by the preceding result.
- Universality: Every graph containing all locally finite path-width-1 graphs must have infinitely many vertices of infinite degree.The proof embeds caterpillars with non-decreasingly growing numbers of leaves and derives a degree contradiction.
4 Graphs with Line-width 1
The section separates line-width, well-order-width, and path-width using infinite stars and caterpillars, and constructs a line-width-1 universal graph.
- Infinite paths: The 2-way infinite path has line-width 1 and well-order-width 2.This supplies the lower-bound example used for the caterpillar's well-order-width.
- Infinite stars: The disjoint union of infinitely many infinite stars has line-width 1, well-order-width 1, and path-width ∞.Each individual infinite star has all three widths equal to 1, but infinitely many disjoint stars force infinite path-width.
- Infinite caterpillars: A caterpillar with a 2-way infinite spine and infinite-degree spine vertices has line-width 1, well-order-width 2, and path-width ∞.The 2-way infinite spine accounts for well-order-width 2.
- Universality: There exists a graph with line-width 1 universal for all graphs of line-width at most 1.The construction is a disjoint union of countably many copies of the infinite-degree caterpillar.
- Universality: Every graph of line-width at most 1 has no cycle or 1-subdivision of K1,3 in any finite subgraph.Consequently, each connected component is shown to be a caterpillar and can embed into the universal construction.
5 Finite Path-width: Proof of Theorem 1
The proof develops well-order-decomposition techniques to convert bounded well-order-width into bounded path-width under restrictions on disjoint infinite paths and infinite-degree vertices.
- Width conversion: If a locally finite graph has no k pairwise disjoint 1-way infinite paths and every component contains one, wow(G) ≤ w implies pw(G) ≤ w + 3(k −1)(w + 1).This is the central conversion lemma used in the characterization proof.
- Width conversion: The proof selects a maximal collection C of pairwise disjoint 1-way infinite paths, with |C| ≤ k −1.Well-order-decomposition intervals are then organized around these paths.
- Well-order structure: For each selected path, a well-order index mP controls the tail behavior of vertices in the decomposition.Earlier indices eventually contain a tail of the path, while the least index containing each vertex is used to track bag membership.
- Width conversion: The resulting global decomposition has width at most w + |C|(3w + 3) ≤ w + 3(k −1)(w + 1).This bound is stated explicitly at the end of the construction.
6 Universal Construction: Proof of Theorem 5
The section constructs universal graphs for bounded line-width through an inductive well-order-width construction, then transfers the resulting quadratic bound to line-width.
- Universality: Every connected graph with well-order-width at most k embeds as a subgraph of U^-_k.The proof selects pairwise disjoint bags, partitions the remaining graph into induced subgraphs of lower well-order-width, and combines inductive embeddings.
- Proof strategy: The argument adapts a finite-graph path-decomposition method: choose pairwise disjoint bags, delete them, and recurse on lower-width subgraphs.This is the structural mechanism behind the inductive embedding proof.
- Construction: The construction U^-_k uses pairwise disjoint sets S_i of size k + 1 and disjoint copies H_i of a universal graph for W_{k−1}.Each S_i is made a clique, and every vertex of H_i is joined to every vertex in S_i ∪ S_{i+1}.
- Well-order-width bound: U^-_k has well-order-width at most k^2 + 3k.The decomposition concatenates decompositions of the H_i and enlarges each bag by adjacent separator sets, yielding width at most k^2 + 3k.
- Universality: The construction extends from connected graphs to all graphs using the componentwise supremum property of well-order-width.Lemma 8 states that a graph’s well-order-width equals the supremum of the well-order-widths of its connected components.
- Theorem 5: A universal graph for L_k exists with line-width at most 4k^2 + 6k.The proof derives this from the inclusion L_k ⊆ W_2k and a universal graph for W_2k with well-order-width at most 4k^2 + 6k.
7 Universal Lower Bound: Proof of Theorem 6
The proof constructs uncountably many pairwise non-isomorphic graphs of path-width k and shows that a universal host of line-width at most k cannot contain them all.
- Constraining a universal host: A line-decomposition of a countable graph can be reduced to countably many distinct bags without increasing its width.The reduction chooses one representative from each repeated-bag equivalence class; countability follows because the bags have size at most k+1.
- Constructing the witness graphs: A k-feasible sequence starts with s_i=i for i∈{1,…,k}, while each later s_i has exactly k allowable choices.The associated sets B_i are built recursively, each having size k+1, and every integer except 1 appears in at least two sets.
- Constructing the witness graphs: The graph G_s joins two vertices exactly when they occur together in some associated set B_i.The sequence of sets forms a path-decomposition of width k, and each B_i induces a (k+1)-clique, so G_s has path-width k.
- Many non-isomorphic witnesses: Distinct k-feasible sequences produce non-isomorphic graphs, and for k≥2 this yields an uncountable family of isomorphism classes.The proof identifies each sequence from the graph structure and combines this with the k choices available at every position after the first k.
- Constraining a universal host: Assuming a universal graph U has line-width at most k, embeddings of all G_s force uncountably many distinct ordered bag pairs in its line-decomposition, a contradiction.The proof uses the monotone bag sequences associated with the embeddings and the fact that each pair determines at most one witness isomorphism class.