Tree-width and Dimension - Part 2

Graph Theory Seminar
Thursday, October 25, 2012 - 12:05pm
1 hour (actually 50 minutes)
Skiles 005
Math, GT
Over the past 40 years, researchers have made many connections between the dimension of posets and the issue of planarity for graphs and diagrams, but there appears to be little work connecting dimension to structural graph theory. This situation has changed dramatically in the last several months. At the Robin Thomas birthday conference, Gwenael Joret, made the following striking conjecture, which has now been turned into a theorem: The dimension of a poset is bounded in terms of its height and the tree-width of its cover graph. In this talk, I will present the proof of this result. The general contours of the argument should be accessible to graph theorists and combinatorists (faculty and students) without deep knowledge of either dimension or tree-width. The proof of the theorem was accomplished by a team of six researchers: Gwenael Joret, Piotr Micek, Kevin Milans, Tom Trotter, Bartosz Walczak and Ruidong Wang.