组合数学 (Fall 2015)/Problem Set 3
Let n 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 n coins with m 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 n coins.)
A set of vertices of graph G(V,E) is a dominating set if for every , it holds that or v is adjacent to a vertex in D. The problem of computing minimum dominating set is NP-hard.
- Prove that for every d-regular graph with n 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 H(W,F) be a graph and n > | W | be an integer. It is known that for some graph G(V,E) such that | V | = n, | E | = m, G does not contain H as a subgraph. Prove that for , there is an edge k-coloring for Kn that Kn contains no monochromatic H.
Remark: Let be the edge set of Kn. "An edge k-coloring for Kn" is a mapping .
Let G(V,E) be a cycle of length and let be a partition of its vertices into n pairwise disjoint subsets, each of cardinality k. For show that there must be an independent set of G containing precisely one vertex from each Vi.
Let be a k-uniform k-regular hypergraph, so that for each there are exact k many having .
Use the probabilistic method to prove: For , there is a 2-coloring such that does not contain any monochromatic hyperedge .