Generalized Lehman–Ron conjecture for directed hypercube layers

Let LiL_i) and LjL_j be layers of the directed hypercube, with i<ji<j and r:=jir:=j-i. Let (S,T;ϕ)(S,T;\phi) be a matched pair with SLiS\subseteq L_i and TLjT\subseteq L_j. Generalized Lehman–Ron conjecture. There are rr collections of vertex-disjoint paths between SS and TT such that their union is edge-disjoint. As the separation between the layers increases, the conjecture predicts proportionally more collections of paths; the paper states that its techniques do not resolve this claim.

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.