Greedy matching in Young's lattice

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)351-366
Number of pages16
JournalOrder
Volume6
Issue number4
DOIs
StatePublished - Dec 1990

Keywords

  • AMS subject classifications (1980): 05A17, 06A10
  • Young's lattice
  • matching
  • partially ordered set

Fingerprint

Dive into the research topics of 'Greedy matching in Young's lattice'. Together they form a unique fingerprint.

Cite this