Abstract
If the level sets of a ranked partially ordered set are totally ordered, the greedy match between adjacent levels is defined by successively matching each vertex on one level to the first available unmatched vertex, if any, on the next level. Aigner showed that the greedy match produces symmetric chains in the Boolean algebra. We extend that result to partially ordered sets which are products of chains. It is widely thought that for Young's lattices corresponding to rectangles, the greedy match is complete. We show here that the greedy match is, in fact, complete for n×2, n×3 and n×4 rectangles but not for n×k rectangles if k≥5 and n is sufficiently large.
Original language | English (US) |
---|---|
Pages (from-to) | 351-366 |
Number of pages | 16 |
Journal | Order |
Volume | 6 |
Issue number | 4 |
DOIs | |
State | Published - Dec 1990 |
Keywords
- AMS subject classifications (1980): 05A17, 06A10
- Young's lattice
- matching
- partially ordered set