Combin.PS3

My Solution for Combinatorics for the Fall 2015 semester, Problem Set 3. Keep your Academic Integrity plz.

Try Firefox if your web browser (e.g. Chrome, IE) does not support MathML, a part of HTML5.

Combinatorics: Problem Set 3

Himemiya

1 Problem 1

1.1

By assigning each coin a distinct integer in [1,n], we can construct a bijection from the weights of different coins to a subset of [n]. Recall that weight of each coin is 0 or 1. For some specific coin which is assigned number i, weights of 0 means iT, weights of 1 means iT. Thus the weights of n coins is mapped to a subset of [n]. Note that the mapping is reversible. Therefore this is a bijection.

Given n coins. If there is a determing collection S1,S2,,Sm[n], we can calculate the m cardinalities by weighing the the coins in Si. Since T can be determined by the m values, the weights of the n coins can also be determined due to the bijection.

1.2

The cardinalities |SiT| must be an integer in [0,n], all the m cardinalites of intersections have at most (n+1)m distinct results. One result of interections can determine at most one subset. Due to the definition of determining and the pigeonhole principle, we have

(n+1)m2n,

i.e.

mnlog2(n+1).

2 Problem 2

2.1

Let S be a set of vertices constructed by randomly including vertex with probability p (p to be determined). Let Y be set of vertices which is neither included in S nor adjacent with a vertex in S. Clearly, SY is a dominating set. By the linearity of expectation,

?[|SY|] =?[|S|]+?[|Y|]
=vVPr[vS]+vVPr[vVd neighbors of vV]
=np+n(1p)d+1.

Let f(p)=p+(1p)d+1, solve f(p)=0 we get p=1(d+1)1/d. Let g(d)=f(p)(1+ln(d+1))/(d+1),

g(d) =1(d+1)1/d+(d+1)(d+1)/d1+ln(d+1)d+1
g(d) =(d+1)1/d2(d((d+1)1/d1)1)ln(d+1)/d.

Note that g(1)=1/4ln(2)/2<0, g(d)0 when d1, limd+g(d)=0. Thus f(p)n(1+ln(d+1))/(d+1) when d1,

?[|SY|]=n×f(p)n(1+ln(d+1))d+1,

i.e. there exists a dominating set with size at most n(1+ln(d+1))d+1.

2.2

Uniformly sample m points as set S. For each vertex i, we define event Ai as vertex i is neither included in S nor adjacent with any vertex in S. Clearly iV,Pr[Ai]=(nd1m)/(nm)(1m/n)d+1, and all the n events depend on other n1 events. By the Lovász Local Lemma, if we make sure

e(1m/n)d+1n1,

there exists a dominating set with size at most m. In another word,

mn(1(en)1/(d+1)).

To compare the two bounds, assuming the new bound is better than previous one, we have

1(en)1/(d+1)(1+ln(d+1))/(d+1)
d+1(dln(d+1))(en)1/(d+1)
n1e(d+1dln(d+1))1/(d+1).

Let f(d)=(d+1dln(d+1))1/(d+1). Note that limd0f(d)=0; f(d)0 when d0; limd+f(d)=1, n must be less than 1/e 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 k-coloring for Kn forms a partition of Kn. Any part of the partition is an edge-induced subgraph of Kn. The only way we know to avoid H is to make sure any subgraph is a subgraph of G or a subgraph of some graph which is isomorphic to G.

Here comes a randomized iterative coloring scheme. In the beginning, all the (n2) edges have not colored. During each iteration, we uniformly rearrange the label of the n vertices at random, and choose a new color for this iteration. For any two vertice which are labelled i and j, if the edge (i,j) has not colored yet and there is an edge (i,j) in G, we color the edge with the color for this iteration.

Clearly any monochromatic subgraph of Kn will be a edge-induced subgraph of some graph which is isomorphic to G, thus Kn will not contain monochromatic H. For each iteration, any edge which has not colored will be colored with probability m/(n2). Hence

Pr[an edge which survives after k times iteration] (n2)Pr[some fixed edge survives after k times iteration]
=n(n1)2(12mn(n1))k
<n(n1)2((12mn(n1))n2/(2m))2lnn
n(n1)2exp(2lnn)
=n(n1)21n2
<12.

Thus all the edge is colored after k times iteration with probability at least 11/2=1/2. Therefore there is an edge k-coloring for Kn that Kn contains no monochromatic H.

4 Problem 4

For each subset Vi we uniformly sample a vertex at random. For each (a,b)E, if Vi s.t. aVibVi, we define a bad event A(a,b) denotes that vertices a and b are sampled so that it fails to sample an independent set of G which contains precisely one vertex from each Vi. Clearly, the mapping between the edges connect different subsets and bad events is bijection.

Any bad event A(a,b) depends on the bad events which have at least a vertex which is in the subset which contains a or b. Since the graph is a cycle, every vertex has degree of 2. For all i{1,2,,n}, the k vertices in Vi is involved in at most 2k bad events. Thus a bad event depends on at most 2*(2k1) events.

Since any bad event happens with probability 1/k2, by the Lovász Local Lemma,

e(1/k2)(4k1)<1,k11,

all bad events does not happen with probablity greater than 0, i.e. there exists an independent set of G containing precisely one vertex from each Vi.

5 Problem 5

Independently assign each vertex 0 or 1 with probablity 1/2 at random. i, define event Ai as all vertices vi is assigned same number. Clearly, i,Pr[Ai]=2×2k=21k. For any hyperedge i, i shares vertex with at most k2 hyperedges. This implies the maximum degree of the dependency graph for the events A1,A2,,A|| is at most k2. Since

e21k(k2+1)

is monotonic decreasing when k>3, and the value of above expression is less than 1 when k10. Due to the Lovász Local Lemma, Pr[Ai¯]>0, i.e. there is a 2-coloring f:V{0,1} s.t. does not contain any monochromatic hyperedge S.

CC BY-SA 4.0 Combin.PS3 by himemeizhi is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.