Combinatorics: Problem Set 3
1 Problem 1
By assigning each coin a distinct integer in , we can construct a bijection from the weights of different coins to a subset of . Recall that weight of each coin is or . For some specific coin which is assigned number , weights of means , weights of means . Thus the weights of coins is mapped to a subset of . Note that the mapping is reversible. Therefore this is a bijection.
Given coins. If there is a determing collection , we can calculate the cardinalities by weighing the the coins in . Since can be determined by the values, the weights of the coins can also be determined due to the bijection.
The cardinalities must be an integer in , all the cardinalites of intersections have at most distinct results. One result of interections can determine at most one subset. Due to the definition of determining and the pigeonhole principle, we have
2 Problem 2
Let be a set of vertices constructed by randomly including vertex with probability ( to be determined). Let be set of vertices which is neither included in nor adjacent with a vertex in . Clearly, is a dominating set. By the linearity of expectation,
Let , solve we get . Let ,
Note that , when , . Thus when ,
i.e. there exists a dominating set with size at most .
Uniformly sample points as set . For each vertex , we define event as vertex is neither included in nor adjacent with any vertex in . Clearly , and all the events depend on other events. By the Lovász Local Lemma, if we make sure
there exists a dominating set with size at most . In another word,
To compare the two bounds, assuming the new bound is better than previous one, we have
Let . Note that ; when ; , must be less than to make the new bound lower than the old bound. This is impossible. Therefore the new bound is worse than previous one.
3 Problem 3
Any edge -coloring for forms a partition of . Any part of the partition is an edge-induced subgraph of . The only way we know to avoid is to make sure any subgraph is a subgraph of or a subgraph of some graph which is isomorphic to .
Here comes a randomized iterative coloring scheme. In the beginning, all the edges have not colored. During each iteration, we uniformly rearrange the label of the vertices at random, and choose a new color for this iteration. For any two vertice which are labelled and , if the edge has not colored yet and there is an edge in , we color the edge with the color for this iteration.
Clearly any monochromatic subgraph of will be a edge-induced subgraph of some graph which is isomorphic to , thus will not contain monochromatic . For each iteration, any edge which has not colored will be colored with probability . Hence
Thus all the edge is colored after times iteration with probability at least . Therefore there is an edge -coloring for that contains no monochromatic .
4 Problem 4
For each subset we uniformly sample a vertex at random. For each , if s.t. , we define a bad event denotes that vertices and are sampled so that it fails to sample an independent set of which contains precisely one vertex from each . Clearly, the mapping between the edges connect different subsets and bad events is bijection.
Any bad event depends on the bad events which have at least a vertex which is in the subset which contains or . Since the graph is a cycle, every vertex has degree of . For all , the vertices in is involved in at most bad events. Thus a bad event depends on at most events.
Since any bad event happens with probability , by the Lovász Local Lemma,
all bad events does not happen with probablity greater than , i.e. there exists an independent set of G containing precisely one vertex from each .
5 Problem 5
Independently assign each vertex or with probablity at random. , define event as all vertices is assigned same number. Clearly, . For any hyperedge , shares vertex with at most hyperedges. This implies the maximum degree of the dependency graph for the events is at most . Since
is monotonic decreasing when , and the value of above expression is less than when . Due to the Lovász Local Lemma, , i.e. there is a -coloring s.t. does not contain any monochromatic hyperedge .
Combin.PS3 by himemeizhi is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.