Show simple item record

dc.contributor.authorStreib, Noah Sametzen_US
dc.date.accessioned2012-06-06T16:50:59Z
dc.date.available2012-06-06T16:50:59Z
dc.date.issued2011-12-16en_US
dc.identifier.urihttp://hdl.handle.net/1853/43744
dc.description.abstractThis 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.en_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectSymmetric chainsen_US
dc.subjectHamiltonian cyclesen_US
dc.subjectCover graphsen_US
dc.subjectHeighten_US
dc.subjectPlanarityen_US
dc.subjectDimensionen_US
dc.subjectPosetsen_US
dc.subject.lcshPartially ordered sets
dc.subject.lcshHamiltonian graph theory
dc.titlePlanar and hamiltonian cover graphsen_US
dc.typeDissertationen_US
dc.description.degreePhDen_US
dc.contributor.departmentMathematicsen_US
dc.description.advisorCommittee Chair: Trotter, William T.; Committee Member: Duffus, Dwight; Committee Member: Sokol, Joel; Committee Member: Tetali, Prasad; Committee Member: Thomas, Robinen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record