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

## Problem 1

(Erdős-Spencer 1974)

Let ${\displaystyle 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 ${\displaystyle S_{1},S_{1},\ldots ,S_{m}\subseteq [n]}$ is called determining if an arbitrary subset ${\displaystyle T\subseteq [n]}$ can be uniquely determined by the cardinalities ${\displaystyle |S_{i}\cap T|,1\leq i\leq m}$.

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

(This gives a lower bound for the number of weighings required to determine the weights of ${\displaystyle n}$ coins.)

## Problem 2

A set of vertices ${\displaystyle D\subseteq V}$ of graph ${\displaystyle G(V,E)}$ is a dominating set if for every ${\displaystyle v\in V}$, it holds that ${\displaystyle v\in D}$ or ${\displaystyle v}$ is adjacent to a vertex in ${\displaystyle D}$. The problem of computing minimum dominating set is NP-hard.

• Prove that for every ${\displaystyle d}$-regular graph with ${\displaystyle n}$ vertices, there exists a dominating set with size at most ${\displaystyle {\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 ${\displaystyle H(W,F)}$ be a graph and ${\displaystyle n>|W|}$ be an integer. It is known that for some graph ${\displaystyle G(V,E)}$ such that ${\displaystyle |V|=n}$, ${\displaystyle |E|=m}$, ${\displaystyle G}$ does not contain ${\displaystyle H}$ as a subgraph. Prove that for ${\displaystyle k>{\frac {n^{2}\ln n}{m}}}$, there is an edge ${\displaystyle k}$-coloring for ${\displaystyle K_{n}}$ that ${\displaystyle K_{n}}$ contains no monochromatic ${\displaystyle H}$.

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

## Problem 4

Let ${\displaystyle G(V,E)}$ be a cycle of length ${\displaystyle k\cdot n}$ and let ${\displaystyle V=V_{1}\cup V_{2}\cup \dots V_{n}}$ be a partition of its ${\displaystyle k\cdot n}$ vertices into ${\displaystyle n}$ pairwise disjoint subsets, each of cardinality ${\displaystyle k}$. For ${\displaystyle k\geq 11}$ show that there must be an independent set of ${\displaystyle G}$ containing precisely one vertex from each ${\displaystyle V_{i}}$.

## Problem 5

(Erdős-Lovász 1975)

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

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