# 组合数学 (Fall 2017)/Problem Set 3

## Problem 1

(Erdős-Spencer 1974)

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.)

## Problem 2

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 .

## Problem 3

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?

## Problem 4

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 .

## Problem 5

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 .

## Problem 6

(Erdős-Lovász 1975)

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 .