Monotonicity testing, routing, and a theorem of Lehman and Ron
summary
States the Lehman–Ron routing theorem: given two same-level subsets S and T of the directed d‑cube with a bijection matching each s to a larger t, there exist |S| vertex‑disjoint S→T paths. Proofs use MaxFlow‑MinCut, complementary slackness and an explicit “inchworm” projection procedure. New claim: when distance ≥2 there are two edge‑disjoint LR solutions (proved); conjecture: distance r yields r edge‑disjoint solutions equivalent to sending r|S| flow with vertex capacity r (generalized LR conjecture), motivated by monotonicity‑testing improvements.
AI-written summary · about