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

## Contents |

## Problem 1

(Erdős-Spencer 1974)

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

## Problem 2

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?

## Problem 3

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 *K*_{n} that *K*_{n} contains no monochromatic *H*.

Remark: Let be the edge set of *K*_{n}. "An edge *k*-coloring for *K*_{n}" is a mapping .

## Problem 4

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 *V*_{i}.

## Problem 5

(Erdős-Lovász 1975)

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 .