William T. Trotter

Over the past 10 years, there has been considerable interest in exploring questions connecting dimension for posets with graph theoretic properties of their cover graphs and order diagrams, especially with the concepts of planarity and treewidth. Joret and Micek conjectured that if $P$ is a poset with a planar cover graph, then the dimension of $P$ is bounded in terms of the number of minimal elements of $P$ and the treewidth of the cover graph of $P$. We settle this conjecture in the affirmative by strengthening a recent breakthrough result [14] by Blake, Micek, and Trotter, who proved that for each poset $P$ admitting a planar cover graph and a unique minimal element we have $\mathrm{dim}(P) \leq 2 \mathrm{se}(P) + 2$, namely, we prove that $\mathrm{dim}(P) \leq 2 \mathrm{wheel}(P) + 2$.

In 1989, Ne\v{s}et\v{r}il and Pudl\'ak posed the following challenging question: Do planar posets have bounded Boolean dimension? We show that every poset with a planar cover graph and a unique minimal element has Boolean dimension at most $13$. As a consequence, we are able to show that there is a reachability labeling scheme with labels consisting of $\mathcal{O}(\log n)$ bits for planar digraphs with a single source. The best known scheme for general planar digraphs uses labels with $\mathcal{O}(\log^2 n)$ bits [Thorup JACM 2004], and it remains open to determine whether a scheme using labels with $\mathcal{O}(\log n)$ bits exists. The Boolean dimension result is proved in tandem with a second result showing that the dimension of a poset with a planar cover graph and a unique minimal element is bounded by a linear function of its standard example number. However, one of the major challenges in dimension theory is to determine whether dimension is bounded in terms of standard example number for all posets with planar cover graphs.

We show that height $h$ posets that have planar cover graphs have dimension $\mathcal{O}(h^6)$. Previously, the best upper bound was $2^{\mathcal{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.

The original notion of dimension for posets was introduced by Dushnik and Miller in 1941 and has been studied extensively in the literature. In 1992, Brightwell and Scheinerman developed the notion of fractional dimension as the natural linear programming relaxation of the Dushnik-Miller concept. In 2016, Ueckerdt introduced the concept of local dimension, and in just three years, several research papers studying this new parameter have been published. In this paper, we introduce and study fractional local dimension. As suggested by the terminology, our parameter is a common generalization of fractional dimension and local dimension. For a pair $(n,d)$ with $2\le d<n$, we consider the poset $P(1,d;n)$ consisting of all $1$-element and $d$-element subsets of $\{1,\dots,n\}$ partially ordered by inclusion. This poset has fractional dimension $d+1$, but for fixed $d\ge2$, its local dimension goes to infinity with $n$. On the other hand, we show that as $n$ tends to infinity, the fractional local dimension of $P(1,d;n)$ tends to a value $\text{FLD}(d)$ which we will be able to determine exactly. For all $d\ge2$, $\text{FLD}(d)$ is strictly less than $d+1$, and for large $d$, $\text{FLD}(d)\sim d/(\log d-\log\log d-o(1))$. As an immediate corollary, we show that if $P$ is a poset, and $d$ is the maximum degree of a vertex in the comparability graph of $P$, then the fractional local dimension of $P$, is at most $2+\text{FLD}(d).$ Our arguments use both discrete and continuous methods.

Previously, Erd\H{o}s, Kierstead and Trotter investigated the dimension of random height~$2$ partially ordered sets. Their research was motivated primarily by two goals: (1)~analyzing the relative tightness of the F\"{u}redi-Kahn upper bounds on dimension in terms of maximum degree; and (2)~developing machinery for estimating the expected dimension of a random labeled poset on $n$ points. For these reasons, most of their effort was focused on the case $0<p\le 1/2$. While bounds were given for the range $1/2\le p <1$, the relative accuracy of the results in the original paper deteriorated as $p$ approaches~$1$. Motivated by two extremal problems involving conditions that force a poset to contain a large standard example, we were compelled to revisit this subject, but now with primary emphasis on the range $1/2\le p<1$. Our sharpened analysis shows that as $p$ approaches~$1$, the expected value of dimension increases and then decreases, answering in the negative a question posed in the original paper. Along the way, we apply inequalities of Talagrand and Janson, establish connections with latin rectangles and the Euler product function, and make progress on both extremal problems.