Gupta–Newman–Rabinovich–Sinclair conjecture on minor-closed flow gaps
A family of finite graphs is considered, and denotes the supremum of over graphs in , where is the multi-commodity max-flow/min-cut gap for . A graph family forbids a minor if there is a graph that is not a minor of any member of the family.
Gupta–Newman–Rabinovich–Sinclair conjecture. For every family of finite graphs , one has
if and only if forbids some minor.
This conjecture characterizes precisely the graph families with uniformly bounded multi-commodity max-flow/min-cut gap, equivalently bounded distortion into distributions over trees. The supplied text does not state whether it has been resolved.
References
Primary source
James R. Lee and Anastasios Sidiropoulos, “Pathwidth, trees, and random embeddings”, arXiv:0910.1409 (2012).
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 1
RemarkAI-assistedClaimed by OpenAI. For each fixed tree-decomposition bag-size bound k, the manuscript claims uniformly bounded L1 distortion for finite connected weighted graph metrics. By the metric-embedding formulation of flow/cut duality, this gives bounded multi-commodity gaps for that bounded-treewidth family. It does not cover all forbidden-minor families or assert the page’s additional tree-distribution equivalence.See full solution
Claimed by OpenAI. For each fixed tree-decomposition bag-size bound k, the manuscript claims uniformly bounded L1 distortion for finite connected weighted graph metrics. By the metric-embedding formulation of flow/cut duality, this gives bounded multi-commodity gaps for that bounded-treewidth family. It does not cover all forbidden-minor families or assert the page’s additional tree-distribution equivalence.
GitHub repository: https://github.com/openai/math
- OpenAI-089-02-L1-Embeddings-of-Graphs-of-Bounded-Treewidth.pdfOpen