Title: On dyadic fractional packings of T-joins
Abstract: We are given a graph G=(V,E) and a nonempty set T of vertices of even size. A T-join is an edge subset whose odd degree vertices coincide with T, and a T-cut is the set of edges between two complementary vertex subsets each containing an odd number of vertices from T. An important theorem of Edmonds and Johnson (1973) proves that the minimum size of a T-cut is equal to the maximum value of a fractional packing of T-joins, where every edge has congestion at most 1. We prove that the fractions assigned to the T-joins can be chosen dyadically, i.e. their denominators are powers of 2. This theorem confirms a dyadic relaxation of the generalized Berge-Fulkerson conjecture. The proof relies on an important theorem of Lovasz (1987) on the matching lattice of matching-covered graphs. In this talk, I will give an overview of the proof, and present some open questions.
Based on joint work with Gerard Cornuejols and Zuzanna Palion (SIDMA 2022).
If you are interested in participating online (either regularly or only in a specific lecture), please contact Yulai Ma or Eckhard Steffen in advance so that the participation link can be shared.