Dimension is polynomial in height for posets with planar cover graphs

06/30/2019
by   Jakub Kozik, et al.
0

We show that height h posets that have planar cover graphs have dimension O(h^6). Previously, this upper bound was 2^O(h^3). 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_5 as a minor.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset