Greedy matching in Young's lattice

Research output: Contribution to journalArticlepeer-review


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
Issue number4
StatePublished - Dec 1990


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


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

Cite this