The forbidden-minor embedding conjecture for graph metrics
The forbidden-minor embedding conjecture for graph metrics
Let be a finite set of graphs. A graph excludes as a minor if it contains no member of as a minor, where minors are obtained by edge contractions, edge deletions, and vertex deletions. Forbidden-minor embedding conjecture. There exists a constant such that every metric on any graph excluding as a minor can be embedded into with distortion at most . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.