Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing

Deeparnab Chakrabarty, C. Seshadhri

Motivated by applications to monotonicity testing, Lehman and Ron (JCTA, 2001) proved the existence of a collection of vertex disjoint paths between comparable sub-level sets in th…