Gupta–Newman–Rabinovich–Sinclair conjecture on minor-closed flow gaps
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.
Sources & referencesView supporting material
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 0
Sign in to submit a solution.
No solutions have been posted yet.