Flow-capacity conjecture for directed hypercube separation distance

Let SS be a source set in the directed hypercube with separation distance rr. Consider a flow network with unit edge capacities and vertex capacities r2r^2. Flow-capacity conjecture. The maxflow is at least

Ω ⁣(rμ+(S)).\Omega\!\left(r\,\mu^+(S)\right).

This would relate edge-capacitated and vertex-capacitated flows in the directed hypercube and is motivated by seeking a flow-based proof of the KMS theorem; the source gives no resolution of the conjecture.

Sources & referencesView supporting material

Primary source

Deeparnab Chakrabarty and C. Seshadhri, “Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing”, arXiv:2409.02206 (2024).

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.