Dimension is polynomial in height for posets with planar cover graphs

2019/06/30 by Kozik, Jakub, Micek, Piotr, Trotter, William T.
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1907.00380

Abstract

We show that height h posets that have planar cover graphs have dimension O(h⁶). Previously, the best upper bound was 2^O(h3). Planarity plays a key role in our arguments, since there are posets such that (1) dimension is exponential in height and (2) the cover graph excludes K₅ as a minor.

Related

• Posets with k-outerplanar cover graphs have bounded dimension
• Planarity and dimension I
• Forcing the Wheel
• Improved bound for the dimension of posets of treewidth two
• Topological minors of cover graphs and dimension