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

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.

Sources & referencesView supporting material

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 0

No solutions have been posted yet.