Minors and dimension

Graph Theory Seminar
Thursday, August 28, 2014 - 1:30pm
1 hour (actually 50 minutes)
Skiles 005
GT, Math and Jagiellonian University in Krakow
The dimension of a poset P is the minimum number of linear extensions of P whose intersection is equal to P. This parameter plays a similar role for posets as the chromatic number does for graphs. A lot of research has been carried out in order to understand when and why the dimension is bounded. There are constructions of posets with height 2 (but very dense cover graphs) or with planar cover graphs (but unbounded height) that have unbounded dimension. Streib and Trotter proved in 2012 that posets with bounded height and with planar cover graphs have bounded dimension. Recently, Joret et al. proved that the dimension is bounded for posets with bounded height whose cover graphs have bounded tree-width. My current work generalizes both these results, showing that the dimension is bounded for posets of bounded height whose cover graphs exclude a fixed (topological) minor. The proof is based on the Robertson-Seymour and Grohe-Marx structural decomposition theorems. I will survey results relating the dimension of a poset to structural properties of its cover graph and present some ideas behind the proof of the result on excluded minors.