Title: A relaxation of Woodall’s conjecture
| Speaker: | Bertrand Guenin |
| Affiliation: | University of Waterloo |
| Location: | MC 5479 |
Abstract: In a directed graph, a directed cut (dicut for short) is a cut where all arcs are directed from one shore to the other; a directed join (dijoin for short) is a set of arcs whose contraction makes the digraph strongly connected. The celebrated Lucchesi–Younger theorem states that for any directed graph the size of the smallest dijoin equals the maximum number of pairwise disjoint dicuts. Woodall’s conjecture posits that the size of the smallest dicut equals the maximum number of pairwise disjoint dijoins.
We show that for every digraph, there exists an integer k, such that after replacing every edge by 2 to the power of k parallel edges, Woodall’s minimax relation holds. This result was motivated by a long-standing conjecture of Paul Seymour, on dyadic dual solutions to integral set covering polyhedra. The proof relies on geometric properties of dyadic points in convex sets, as well graph theoretical arguments.
This is joint work with former graduate student Steven Hwang.