Discrete Math Seminar Spring 2009
Fisher's proof for tournaments of Seymour's 2nd neighborhood conjecture
Stephen Hartke, UNL;
Jan 13
Seymour conjectured that for every simple digraph G (no loops and no cycles of length 2), G has a vertex v such that the number of vertices at distance at most 2 from v is at least twice the outdegree of v. Dean made the same conjecture for tournaments. We will present Fisher's 1996 proof of Dean's conjecture. The proof is probabilistic and uses linear programming.