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

From EtoneWiki
Jump to: navigation, search

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

Personal tools