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

From EtoneWiki
Jump to: navigation, search

Problem 1

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

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 3

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 4

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 .

Problem 5

(Erdős-Lovász 1975)

Let be a -uniform -regular hypergraph, so that for each there are exact many having .

Use the probabilistic method to prove: For , there is a 2-coloring such that does not contain any monochromatic hyperedge .