Every finite distributive lattice is a set of stable matchings for a small stable marriage instance (Q1821125): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0097-3165(87)90037-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2003618558 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5331549 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Every finite distributive lattice is a set of stable matchings / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4165427 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: College Admissions and the Stability of Marriage / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Complexity of Counting Stable Marriages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4130997 / rank | |||
Normal rank |
Latest revision as of 19:20, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Every finite distributive lattice is a set of stable matchings for a small stable marriage instance |
scientific article |
Statements
Every finite distributive lattice is a set of stable matchings for a small stable marriage instance (English)
0 references
1987
0 references
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.
0 references
stable marriage problem
0 references
preference list
0 references
weak dominance
0 references
partial order
0 references
finite distributive lattice
0 references
meet-irreducibles
0 references