Bounded Treewidth Guarantees Finite-Distortion L1 Embeddings

The manuscript’s theorem is that, for every fixed bag-size bound (k \ge 2), there is a finite constant (C_k) such that every finite, connected, undirected graph admitting a tree decomposition with bags of at most (k) vertices has an embedding into finite-dimensional real (L_1) satisfying, for every pair of vertices (u,v),

Here (d(u,v)) is the length of a shortest route along the graph’s edges, and (L_1) distance is the sum of absolute coordinate differences. The graph’s edge lengths can be any positive real numbers. After rescaling, no distance shrinks, and none expands by more than (C_k).^†

The constant depends on the bag-size bound, but not on the number of graph vertices, the depth of the decomposition, or the ratios between edge lengths. The embedding uses finitely many coordinates, though the dimension may grow. The proof establishes that (C_k) exists; it does not provide an explicit estimate for how it depends on (k).

The essential distinction is between local structure and global size. Bounded treewidth does not require the graph itself to be a tree: cycles, including triangles, are allowed. Instead, the vertices are arranged in overlapping bags whose connections form a tree. Each graph edge must have both endpoints in some bag, and all bags containing a given vertex must be connected in the decomposition tree. Bags of size at most (k) correspond to treewidth at most (k-1); the tree of bags can still branch and extend deeply.

The proof constructs distances by adding weighted cuts. A cut labels every vertex zero or one; a pair receives the cut’s weight when its labels differ, and zero otherwise. Summing over cuts gives an (L_1) distance, since each weighted label is a coordinate. But any one cut can put two far-apart vertices on the same side. Controlling the sum from above is not enough: the construction must also prevent pairs from collapsing.

The manuscript first imposes consistency locally. Each bag has a measure on its binary label assignments, and neighboring bags must agree on the full distribution of labels over their shared vertices. Because the bags form a tree, the distributions can be glued by conditional sampling while preserving each bag’s law. If the resulting cuts bound distances across every edge from above, that bound extends along shortest paths.

But consistent local laws alone do not guarantee a lower bound between distant vertices. The proof therefore combines two protections: reservations that preserve useful cuts along paths, and anchor cuts that test separation at selected locations. The first addresses pairs sharing a bag; the second helps ensure separation survives globally.

The construction represents cuts using particles: each particle assigns a real height to every vertex, and a threshold sweep labels vertices above the threshold one and the rest zero. Two vertices receive different labels exactly for thresholds between their heights. Thus the amount of cut mass distinguishing them is their absolute height difference.

The key update changes heights away from a bag while preserving the bag’s complete assignment law. Take two particles with the same weak ordering of heights on the bag and average their heights. Each interval between consecutive heights measures a difference, so the two original interval masses add to twice the mass for the average. The endpoint intervals obey the same identity when the cutoff is shared. Two copies of the average therefore preserve the mass of every assignment supported by the sweep. Now add a perturbation that is zero on the bag to one copy and subtract it from the other. The bag law remains unchanged, but the heights elsewhere can separate.

This update lets the construction alter particle heights beyond a bag without disrupting the local laws that must agree across the decomposition. A reservation then freezes a particle pair along a path of bags, keeping its cut measures present in every bag law on that path. At launch, the particles agree on the bag. For each full assignment of labels on that bag, the construction compares the masses of the two possible labels for a distant vertex and keeps the smaller. Summing these minima measures the remaining uncertainty about that vertex; the manuscript shows it is at least twice the perturbation’s magnitude there.

When the launch bag lies on the path between the tested endpoints, the manuscript uses a published bounded-state Markov-flow theorem to turn that uncertainty into separation. The loss depends on bag size, not path length.

Reservations at relevant distance scales separate pairs that share a bag. The second construction uses a bounded list of anchors: its cuts are based on distance from an anchor plus localized random noise. Crucially, the retention choices are fixed from the metric before the noise is sampled.

Suppose a sequence of pairs had combined cut distance collapsing relative to graph distance. Normalize one endpoint’s distance from the least common ancestor bag. A compactness argument then produces a youngest reservation that survives from bags a definite distance away to bags approaching the endpoint. The noise tests force an earlier testing bag to protect a younger surviving reservation, contradicting its being the youngest.

The contradiction supplies a positive uniform lower factor, while the edge bounds supply a finite upper factor. Combining the two cut measures and scaling their weights yields finite-dimensional (L_1) coordinates, with one coordinate for each subset of the vertex set. The result establishes the bounded-treewidth case of the Gupta–Newman–Rabinovich–Sinclair conjecture, not the full conjecture.