Speaker:

Siyue Liu (Carnegie Mellon University)

Time:

• 16:20-17:20 Beijing Time
• Dec 13, 2024 (Friday)

Venue:

518, Research Building 4

Abstract:

In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects each dicut. Woodall conjectured in 1976 that in every digraph, the minimum size of a dicut equals to the maximum number of disjoint dijoins. However, prior to our work, it was not even known if at least 3 disjoint dijoins exist in an arbitrary digraph whose minimum dicut size is sufficiently large. By building connections with nowhere-zero (circular) k-flows, we prove that every digraph with minimum dicut size \tau contains \tau/k disjoint dijoins if the underlying undirected graph admits a nowhere-zero (circular) k-flow. The existence of nowhere-zero 6-flows in 2-edge-connected graphs (Seymour 1981) directly leads to the existence of \tau/6 disjoint dijoins in any digraph with minimum dicut size tau, which can be found in polynomial time as well. The existence of nowhere-zero circular (2+1/p)-flows in 6p-edge-connected graphs (Lovász et al 2013) directly leads to the existence of \tau p/(2p+1) disjoint dijoins in any digraph with minimum dicut size tau whose underlying undirected graph is 6p-edge-connected.

Speaker Bio:

Siyue Liu is a Ph.D. student in the Algorithms, Combinatorics, and Optimization program at the Tepper School of Business, Carnegie Mellon University. Her research focuses on combinatorial optimization and integer programming. She has published in Mathematical Programming and received the Best Paper Award at IPCO.