ITLApplied  Computational Mathematics Division
ACMD Seminar Series
Attractive Image NIST

Dimension and Height for Posets with Planar Cover Graphs

Noah Streib
Applied and Computational Mathematics Division, NIST

Tuesday, January 22, 2013 15:00-16:00,
Building 101, Lecture Room C
Tuesday, January 22, 2013 13:00-14:00,
Room 1-4058


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.

Contact: B. Cloteaux

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

Privacy Policy | Disclaimer | FOIA
NIST is an agency of the U.S. Commerce Department.
Last updated: 2012-10-15.