Gupta–Newman–Rabinovich–Sinclair conjecture on minor-closed flow gaps
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.