Every finite distributive lattice is a set of stable matchings for a small stable marriage instance (Q1821125)

An instance of the stable marriage problem consists of n men and n women, each of whom has a rank ordered preference list of the persons of the opposite sex. A marriage M is a one-to-one matching of the men and the women. M is stable provided there is no pair (man,woman) which would prefer each other over their M-assigned partners but are not matched by M. Given two marriages M and M', M weakly dominates M' iff no man prefers his M'-mate over his M-mate. The set of all stable marriages (on a given instance) is a distributive lattice under weak dominance as partial order [\textit{D. E. Knuth}, Mariages stables (Les Presses de l'Université de Montréal, 1976; Zbl 0358.68057)]. \textit{C. Blair} [J. Comb. Theory, Ser. A 37, 353-356 (1984; Zbl 0546.06009)] established the converse result. Given a k-element distributive lattice, he constructed a problem instance with \(n=2^ k.\) The present note exploits the well-known isomorphism between a finite distributive lattice and the family of all lower ends of the poset of its meet-irreducibles (under set inclusion) to obtain much better bounds. The problem instance constructed satisfies \(n\leq (k^ 2-k+4)\) (Theorem 1); moreover, if \(n_ 0\) is the minimal number of men (and women) in any problem instance realizing the given lattice, then the instance constructed in this note satisfies \(n\leq n^ 4_ 0/8\) (Theorem 3). No proofs are given.