Gupta–Newman–Rabinovich–Sinclair conjecture on minor-closed flow gaps

About 17 years old · traced to

A family of finite graphs is considered, and c1(F)c_1(\mathcal F) denotes the supremum of c1(G)c_1(G) over graphs GG in F\mathcal F, where c1(G)c_1(G) is the multi-commodity max-flow/min-cut gap for GG. 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 F\mathcal F, one has

c1(F)<∞c_1(\mathcal F)<\infty

if and only if F\mathcal F 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

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 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 solutionHide 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

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/L1-Embeddings-of-Graphs-of-Bounded-Treewidth-September-23-2026/paper.pdf

  • OpenAI-089-02-L1-Embeddings-of-Graphs-of-Bounded-Treewidth.pdf462,080 bytesOpen