ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.