Reference no: EM13926955

1. Let A be a finite set with subsets A1, ..., An, and let d1, ..., dn ∈ N. Show that there are disjoint subsets Dk ⊆ Ak, with |Dk| = dk for all k ≤ n, if and only if | S i∈I Ai | ≥ P i∈I di for all I ⊆ {1, ..., n}.

Hint: Construct a bipartite graph in which A is one side, and the other side consists of a suitable number of copies of the sets Ai . Define the edge set of the graph so that the desired result can be derived from the marriage theorem.

2. Find a bipartite graph with a set of preferences such that no matching of maximum size is stable and no stable matching has maximum size. Find a non-bipartite graph with a set of preferences that has no stable matching.

Hint: Try C 6 . Change occurs most likely if unhappy vertices can bring it about without having to ask the happy ones. (If philosophy does not help, try K3 .)