组合数学 (Spring 2014)/Problem Set 2

From EtoneWiki
Jump to: navigation, search

Problem 1

Prove the following identity:

  • .

(Hint: Use double counting.)

Problem 2

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

Hint: you can use Lovász Local Lemma.