The forbidden-minor embedding conjecture for graph metrics

Let LL be a finite set of graphs. A graph excludes LL as a minor if it contains no member of LL as a minor, where minors are obtained by edge contractions, edge deletions, and vertex deletions. Forbidden-minor embedding conjecture. There exists a constant CL<C_L<\infty such that every metric on any graph excluding LL as a minor can be embedded into 1\ell_1 with distortion at most CLC_L. This conjecture generalizes the Planar Conjecture and remains open despite substantial work on low-distortion embeddings of graph metrics.

Sources & referencesView supporting material

Primary source

Mikhail I. Ostrovskii and Beata Randrianantoanina, “A new approach to low-distortion embeddings of finite metric spaces into non-superreflexive Banach spaces”, arXiv:1609.06618 (2017).

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.