Title: Seymour's Second Neighborhood Conjecture
Speaker: Michael Donders, Rutgers University
Date: Wednesday, September 24, 2014 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
First proposed by Paul Seymour in 1990, Seymour's Second Neighborhood conjecture is a relatively simple sounding statement that has proved surprisingly difficult to verify. The conjecture states that for every simple directed graph, there exists a vertex whose second neighborhood is at least as large as its first neighborhood. This talk will go over the trickiness that is involved with directed graph neighborhoods, as well as the progress and partial results that have accumulated over this conjecture. Further we will discuss the relevance of the Second Neighborhood Conjecture to other important conjectures in directed graph theory, including the Caccetta-Häggkvist Conjecture and the Behzad-Chartrand-Wall Conjecture.