Title: Disjoint Dijoins
Speaker: Paul Seymour, Princeton University
Date: Tuesday, September 17, 2013 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
A "dijoin" in a digraph is a set of edges meeting all directed cuts. The Lucchesi-Younger theorem says that if every dijoin has size at least k, then there are k pairwise disjoint directed cuts, and in 1976 Woodall proposed a dual statement, that if every directed cut has size at least k then there are k pairwise disjoint dijoins. This is still open. But Schrijver showed that it becomes false if we give the edges nonnegative integer capacities; it is not always true that if every directed cut has total capacity at least k, then there are k dijoins using each edge at most its capacity. In Schrijver's example, and in all others known, the edges with positive capacity form a disconnected graph, and perhaps the capacitated version is true if they form a connected graph. We have several partial results on this. Joint work with Maria Chudnovsky, Katherine Edwards, Ringi Kim and Alex Scott.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math