Planar Posets, Dimension, Breadth and the Number of Minimal Elements

摘要

In recent years, researchers have shown renewed interest in combinatorial properties of posets determined by geometric properties of its order diagram and topological properties of its cover graph. In most cases, the roots for the problems being studied today can be traced back to the 1970's, and sometimes even earlier. In this paper, we study the problem of bounding the dimension of a planar poset in terms of the number of minimal elements, where the starting point is the 1977 theorem of Trotter and Moore asserting that the dimension of a planar poset with a single minimal element is at most 3. By carefully analyzing and then refining the details of this argument, we are able to show that the dimension of a planar poset with t minimal elements is at most 2t + 1. This bound is tight for t = 1 and t = 2. But for t a parts per thousand yen 3, we are only able to show that there exist planar posets with t minimal elements having dimension t + 3. Our lower bound construction can be modified in ways that have immediate connections to the following challenging conjecture: For every d a parts per thousand yen 2, there is an integer f(d) so that if P is a planar poset with dim(P) a parts per thousand yen f(d), then P contains a standard example of dimension d. To date, the best known examples only showed that the function f, if it exists, satisfies f(d) a parts per thousand yen d + 2. Here, we show that lim (d -> a) f(d)/d a parts per thousand yen >= 2.