组合数学 (Spring 2014)/Problem Set 2
Prove the following identity:
(Hint: Use double counting.)
Let coins of weights 0 and 1 be given. We are also given a scale with which we may weigh any subset of the coins. Our goal is to determine the weights of coins (that is, to known which coins are 0 and which are 1) with the minimal number of weighings.
This problem can be formalized as follows: A collection is called determining if an arbitrary subset can be uniquely determined by the cardinalities .
- Prove that if there is a determining collection , then there is a way to determine the weights of coins with weighings.
- Use pigeonhole principle to show that if a collection is determining, then it must hold that .
(This gives a lower bound for the number of weighings required to determine the weights of coins.)
A set of vertices of graph is a dominating set if for every , it holds that or is adjacent to a vertex in . The problem of computing minimum dominating set is NP-hard.
- Prove that for every -regular graph with vertices, there exists a dominating set with size at most .
- Try to obtain an upper bound for the size of dominating set using Lovász Local Lemma. Is it better or worse than previous one?
Let be a graph and be an integer. It is known that for some graph such that , , does not contain as a subgraph. Prove that for , there is an edge -coloring for that contains no monochromatic .
Remark: Let be the edge set of . "An edge -coloring for " is a mapping .
Let be a cycle of length and let be a partition of its vertices into pairwise disjoint subsets, each of cardinality . For show that there must be an independent set of containing precisely one vertex from each .
Hint: you can use Lovász Local Lemma.