| Popis: |
Blair (J. Combin. Theory Ser. A 37 (1984), 353–356) showed that every finite distributive lattice is the weak dominance relation for some instance of the stable marriage problem, but the only bound given on the size of the instance was 2k for a k element lattice. In this note we describe a method which, for any distributive lattice L of k elements, constructs an instance of size at most k2 − k + 4. Further, we note that if the smallest instance for lattice L has size 2n, then the construction in this paper has size at most n 4 4 . |
