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

About 1 year old · traced to

For L,C∈NL,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,C∈NL,C\in\mathbb{N}, there exists C′∈NC'\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.

References

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.