Openly Disjoint Paths, Jump Systems, and Discrete Convexity
Presenter
March 30, 2023
Abstract
In 1978, Mader discovered a min-max theorem on the number of openly disjoint paths between terminals. Sadli and Sebo (2000) showed that the set of integer vectors in that appear as degree sequences of openly disjoint paths forms a jump system. In this talk, we describe an alternative proof of this fact by using a reduction to matroid matching, which was originally observed by Lovasz (1980). In addition, we show that a function on this jump system determined by the minimum total length of openly disjoint paths enjoys the M-convexity introduced by Murota (2006).