Nguyen–Scott–Seymour edge-weighting conjecture for graph quasi-isometries

For L,CNL,C\in \mathbb{N}, let GG and HH be graphs and let φ\varphi be an (L,C)(L,C)-quasi-isometry from GG to HH. An edge-weighting function w ⁣:E(H)Nw\colon E(H)\to\mathbb{N} gives HH the weighted-graph metric, denoted (H,w)(H,w).

Nguyen–Scott–Seymour conjecture. For all L,CNL,C\in\mathbb{N}, there exists CNC'\in\mathbb{N} such that if φ\varphi is an (L,C)(L,C)-quasi-isometry from a graph GG to a graph HH, then there is an edge-weighting function w ⁣:E(H)Nw\colon E(H)\to\mathbb{N} such that the same function φ\varphi is a (1,C)(1,C')-quasi-isometry from GG to the weighted graph (H,w)(H,w).

The conjecture asserts that suitable positive integer edge weights can remove multiplicative distortion while retaining only bounded additive distortion. The paper proves that this general formulation is false by constructing counterexamples, so it is refuted.

Sources & referencesView supporting material

Primary source

James Davies, Meike Hatzel and Robert Hickingbotham, “Quasi-isometries between graphs with variable edge lengths”, arXiv:2503.07448 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.