Date: Monday, February 04, 2013
Location: 3088 East Hall (4:00 PM to 5:00 PM)
Title: The Seymour-Robertson Theorem and Graph Minor Theory
Abstract: In the 1930s, Klaus Wagner conjectured that in any infinite set of finite undirected graphs, there exist two graphs on the list such that one graph is isomorphic to a minor of the other. Neil Robertson and Paul Seymour proved Wagner's Conjecture (now the Seymour-Robertson Theorem) over the course of twenty papers published between 1983 and 2004. While the statement of this theorem may seem inconspicuous at first, the Seymour-Robertson Theorem, and its proof, have had a huge impact on graph theory. For example, this theorem guarantees the existence of a polynomial time algorithm for testing any minor-closed property of graphs, such as embeddability on a fixed closed, compact surface. In this talk, we will discuss some of the ideas behind the proof of this theorem, and some of its consequences. We will not assume any previous background in graph theory.
Speaker: Alex Leaf
Institution: UM
Event Organizer:
|
