Dimension and Height for Posets with Planar Cover Graphs

We show that for each positive integer $h$, there exists a least positive integer $c(h)$ so that if $P$ is a poset having a planar cover graph and height $h$, then the dimension of $P$ is at most $c(h)$. Trivially, $c(1)$ is 2. In 2010, Felsner, Li and Trotter showed that $c(2)$ is 4. However, their proof techniques do not apply when $h$ is at least 3. Here, we focus on establishing the existence of $c(h)$ for $h$ at least 3, although we suspect that the upper bound provided by our proof is far from best possible. From below, a construction of Kelly is easily modified to show that $c(h)$ must be at least $h + 2$.

Speaker Bio: Noah Streib received his BA in mathematics from Oberlin College in the spring of 2006. Later that year, he started his graduate work at Georgia Tech in the Algorithms, Combinatorics, and Optimization program. Streib graduated with his PhD in the spring of 2012 under the advisement of William T. Trotter. In July of 2012, he began his NRC postdoc at NIST with Isabel Beichl.

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3668; at least 24 hours in advance.