Wednesday, June 19
What could cause a directed graph not to possess many pairwise vertex-disjoint directed circuits? It might be that there is a small set of vertices so that every directed circuit passes through at least one of these vertices. In 1973 Younger conjectured that there was no other possible cause; more precisely, that in in every digraph without many disjoint directed circuits there is a small set of vertices meeting all directed circuits. We sketch a recent proof of this conjecture.This is joint work with Bruce Reed, Neil Robertson and Robin Thomas.
Paul D. Seymour