Piotr Micek
title: Planarity and dimension
The dimension of a partially ordered set P (poset for short) is the
minimum positive integer d such that P is isomorphic to a subposet of
R^d with the natural product order.
Dimension is arguably the most widely studied measure of complexity of
posets and standard examples in posets are the canonical structure
forcing dimension to be large.
In many ways, dimension for posets is analogous to chromatic number
for graphs with standard examples in posets playing the role of
cliques in graphs.
However, planar graphs have chromatic number at most four, while
posets with planar diagrams may have arbitrarily large dimension.
The key feature of all known constructions is that large dimension is
forced by a large standard example.
Since the early 1980s, the question of whether every poset of large
dimension and a planar diagram contains a large standard example has
been a critical challenge in posets theory with very little progress
over the years.
More recently, the analogous question has been considered for the
broader class of posets with planar cover graphs.
We answer both questions in the affirmative by proving that for every poset P:
(1) if P has a planar diagram, then dim(P) <= 128 se(P) + 512, and
(2) if P has a planar cover graph, then dim(P) = O( se^8(P) ), where
dim(P) stands for the dimension of P and se(P) stands for the maximum
order of a standard example in P.
Joint work with Heather Blake, Jędrzej Hodor, Michał Seweryn and
William T. Trotter.