Greedy matching in Young's lattice (Q1813931)

If the two vertex sets of a bipartite graph are (totally) ordered, the greedy match on the graph is defined by successively matching each vertex on one set to the first available unmatched vertex, if any, on the other set. The greedy matching on posets with totally ordered levels is defined with the previous process for every pair of adjacent levels. \textit{M. Aigner} showed [J. Combinat. Theory, Ser. B 14, 187-194 (1973; Zbl 0274.05003)] that the greedy match produces symmetric chains in Boolean algebras. This paper extends Aigner's result to posets of products of chains, giving a new proof for Aigner's result as well. It also proves that greedy match is complete for Young's lattice in the case of \(n\times 2\), \(n\times 3\) and \(n\times 4\) rectangles, but disproves it for rectangles of the form \(n\times k\), \(k\geq 5\) and \(n\) big enough. The proofs are elementary but not easy.