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

## 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 $S_1,S_1,\ldots,S_m\subseteq [n]$ is called determining if an arbitrary subset $T\subseteq[n]$ can be uniquely determined by the cardinalities $|S_i\cap T|, 1\le i\le m$.

• Prove that if there is a determining collection $S_1,S_1,\ldots,S_m\subseteq [n]$, then there is a way to determine the weights of n coins with m weighings.
• Use pigeonhole principle to show that if a collection $S_1,S_1,\ldots,S_m\subseteq [n]$ is determining, then it must hold that $m\ge \frac{n}{\log_2(n+1)}$.

(This gives a lower bound for the number of weighings required to determine the weights of n coins.)

## Problem 2

A set of vertices $D\subseteq V$ of graph G(V,E) is a dominating set if for every $v\in V$, it holds that $v\in D$ 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 $\frac{n(1+\ln(d+1))}{d+1}$.
• 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 $k>\frac{n^2\ln n}{m}$, there is an edge k-coloring for Kn that Kn contains no monochromatic H.

Remark: Let $E=\binom{V}{2}$ be the edge set of Kn. "An edge k-coloring for Kn" is a mapping $f:E\to[k]$.

## Problem 4

Let G(V,E) be a cycle of length $k\cdot n$ and let $V=V_1\cup V_2\cup\dots V_n$ be a partition of its $k\cdot n$ vertices into n pairwise disjoint subsets, each of cardinality k. For $k\ge 11$ show that there must be an independent set of G containing precisely one vertex from each Vi.

## Problem 5

(Erdős-Lovász 1975)

Let $\mathcal{H}\subseteq{V\choose k}$ be a k-uniform k-regular hypergraph, so that for each $v\in V$ there are exact k many $S\in\mathcal{H}$ having $v\in S$.

Use the probabilistic method to prove: For $k\ge 10$, there is a 2-coloring $f:V\rightarrow\{0,1\}$ such that $\mathcal{H}$ does not contain any monochromatic hyperedge $S\in\mathcal{H}$.