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.)
Let be a -uniform hypergraph with vertex set . A blocking set for is a set of vertices such that every hyperedge intersects with , i.e. .
In particular, when , the hypergraph degenerates to a graph, and a blocking set is now a vertex cover. Indeed, the notion of blocking set is a generalization of vertex cover to hypergraphs. Like the minimum vertex cover problem, finding a minimum blocking set for a hypergraph is NP-hard.
- Prove this: For any hypergraph with , there is a blocking set of size at most .
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 .
Let be a -uniform -regular hypergraph, so that for each there are exact many having .
Use the probabilistic method to prove: For , there is a 2-coloring such that does not contain any monochromatic hyperedge .