School Seminars and Colloquia

The grid minor theorem, part 1

Discrete Structures and Algorithms (Reading Group): Graph Minors

by David Wood


Institution: The University of Melbourne
Date: Mon 24th October 2011
Time: 11:00 AM
Location: Room 107, Richard Berry Building

Abstract: The grid minor theorem states that every graph with sufficiently large treewidth contains a k x k grid as a minor. This result is of fundamental importance in graph theory. Over the next month we will prove this result, following the proof given in Diestel's textbook (Theorem 12.4.4). The goal of this talk is to complete the proof of Lemma 12.4.5. The talk will be most beneficial if you attempt to read the proof ahead of time. See http://www.ms.unimelb.edu.au/~woodd/PAPERS/Books/Diestel4-Chapter12.pdf