| Speaker: |
Mahtab Alghasi |
| Affiliation: | University of Waterloo |
| Room: | MC 6029 |
Abstract: Let G be a graph and let T be a nonempty set of vertices of even cardinality. A T-join is an edge set whose odd-degree vertices are precisely T, and a T-cut is a cut with an odd number of terminals on each side. A classical consequence of the Edmonds–Johnson theorem is that the minimum cardinality of a T-cut equals the maximum value of a fractional packing of T-joins. An optimal packing need not be integral or even half-integral, but can its coefficients always be chosen with denominators that are powers of two?
I’ll present the affirmative answer of Ahmad Abdi, Gérard Cornuéjols, and Zuzanna Palion, which establishes Seymour’s Dyadic Conjecture for clutters of T-joins. I’ll outline how the proof combines Lovász’s matching-lattice theorem with dyadic feasibility and combinatorial contraction and gluing arguments.
*We switched to a closely related topic after learning that the author will present the work the following day, Tuesday, November 24, at 6:30 p.m. Eastern. For those interested you can also join the talk online. Sorry for any inconvenience caused by the change. https://researchseminars.org/seminar/SFUOR