Chain and antichain enumeration in posets, and b-ary partitions

The Greene-Kleitman theorem says that the lengths of chains and antichains in any poset are intimately related via an integer partition, but very little is known about the partition [lambda](P) for most posets P. Our first goal is to develop a method for calculating values of [lambda]k(P) for certain posets. We find the size of the largest union of two or three chains in the lattice of partitions of n under dominance order, and in the Tamari lattice. Similar techniques are then applied to the k-equal partition lattice. We also present some partial results and conjectures on chains and antichains in these lattices. We give an elementary proof of the rank-unimodality of L(2, n, m), and find a symmetric chain decomposition of L(2, 2, m). We also present some partial results and conjectures about related posets, including a theorem on the size of the largest union of k chains in these posets and a bijective proof of the symmetry of the H-vector for 2 x n. We answer a question of Knuth about the existence of a Gray path for binary partitions, and generalize to b-ary partitions when b is even. We also discuss structural properties of the posets Rb(n), and compute some chain and antichain lengths in the subposet of join-irreducibles.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Mathematics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2004

Author dc:creator

• Early, Edward Fielding, 1977-

Advisor dc:contributor.advisor

• Richard P. Stanley.

• Mathematics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/30148

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/30148