The GNRS conjecture on graph families and minor exclusion

For a graph family F\mathcal F, let c1(F)c_1(\mathcal F) denote the supremum of the least distortion needed to embed its members into L1L_1.

GNRS conjecture. For every family of finite graphs F\mathcal F, one has c1(F)=O(1)c_1(\mathcal F)=O(1) if and only if F\mathcal F forbids some minor.

The conjecture would characterize graph families with uniformly bounded L1L_1-embedding distortion, equivalently those with uniformly bounded multi-commodity flow/cut gap. It generalizes the planar embedding problem and remains open.

Sources & referencesView supporting material

Primary source

Anastasios Sidiropoulos, “Non-positive curvature, and the planar embedding conjecture”, arXiv:1304.7512 (2013).

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.