Back to search

Georgia Institute of Technology

Planar and hamiltonian cover graphs

Abstract

dc:description.abstract

This dissertation has two principal components: the dimension of posets with planar cover graphs, and the cartesian product of posets whose cover graphs have hamiltonian cycles that parse into symmetric chains. Posets of height two can have arbitrarily large dimension. In 1981, Kelly provided an infinite sequence of planar posets that shows that the dimension of planar posets can also be arbitrarily large. However, the height of the posets in this sequence increases with the dimension. In 2009, Felsner, Li, and Trotter conjectured that for each integer h at least 2, there exists a least positive integer c(h) so that if P is a poset with a planar cover graph (the class of posets with planar cover graphs includes the class of planar posets) and the height of P is h, then the dimension of P is at most c(h). In the first principal component of this dissertation we prove this conjecture. We also give the best known lower bound for c(h), noting that this lower bound is far from the upper bound. In the second principal component, we consider posets with the Hamiltonian Cycle--Symmetric Chain Partition (HC-SCP) property. A poset of width w has this property if its cover graph has a hamiltonian cycle which parses into w symmetric chains. This definition is motivated by a proof of Sperner's theorem that uses symmetric chains, and was intended as a possible method of attack on the Middle Two Levels Conjecture. We show that the subset lattices have the HC-SCP property by showing that the class of posets with the strong HC-SCP property, a slight strengthening of the HC-SCP property, is closed under cartesian product with a two-element chain. Furthermore, we show that the cartesian product of any two posets from this strong class has the (weak) HC-SCP property.

Degree

thesis:*
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2011

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Streib, Noah Sametz
Advisor dc:contributor.advisor
  • Trotter, William T.
Committee members dc:contributor.committeemember
  • Duffus, Dwight
  • Sokol, Joel
  • Tetali, Prasad
  • Thomas, Robin

Subjects

dc:subject × 9

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/43744

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Streib, Noah Sametz. Planar and hamiltonian cover graphs. Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/43744