概率论 (Summer 2013)/Problem Set 3

Problem 1

A set of vertices [math]\displaystyle{ D\subseteq V }[/math] of graph [math]\displaystyle{ G(V,E) }[/math] is a dominating set if for every [math]\displaystyle{ v\in V }[/math], it holds that [math]\displaystyle{ v\in D }[/math] or [math]\displaystyle{ v }[/math] is adjacent to a vertex in [math]\displaystyle{ D }[/math]. The problem of computing minimum dominating set is NP-hard.

• Prove that for every [math]\displaystyle{ d }[/math]-regular graph with [math]\displaystyle{ n }[/math] vertices, there exists a dominating set with size at most [math]\displaystyle{ \frac{n(1+\ln(d+1))}{d+1} }[/math].

• 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? Why?

Problem 2

Let [math]\displaystyle{ H(W,F) }[/math] be a graph and [math]\displaystyle{ n\gt |W| }[/math] be an integer. It is known that for some graph [math]\displaystyle{ G(V,E) }[/math] such that [math]\displaystyle{ |V|=n }[/math], [math]\displaystyle{ |E|=m }[/math], [math]\displaystyle{ G }[/math] does not contain [math]\displaystyle{ H }[/math] as a subgraph. Prove that for [math]\displaystyle{ k\gt \frac{n^2\ln n}{m} }[/math], there is an edge [math]\displaystyle{ k }[/math]-coloring for [math]\displaystyle{ K_n }[/math] that [math]\displaystyle{ K_n }[/math] contains no monochromatic [math]\displaystyle{ H }[/math].

Remark: Let [math]\displaystyle{ E=\binom{V}{2} }[/math] be the edge set of [math]\displaystyle{ K_n }[/math]. "An edge [math]\displaystyle{ k }[/math]-coloring for [math]\displaystyle{ K_n }[/math]" is a mapping [math]\displaystyle{ f:E\to[k] }[/math].

Problem 3

Let [math]\displaystyle{ G(V,E) }[/math] be a cycle of length [math]\displaystyle{ 4n }[/math] and let [math]\displaystyle{ V=V_1\cup V_2\cup\dots V_n }[/math] be a partition of its [math]\displaystyle{ 4n }[/math] vertices into [math]\displaystyle{ n }[/math] pairwise disjoint subsets, each of cardinality 4. Is it true that there must be an independent set of [math]\displaystyle{ G }[/math] containing precisely one vertex from each [math]\displaystyle{ V_i }[/math]? (Prove or supply a counter example.)

Hint: you can use Lovász Local Lemma.

Problem 4

(Due to D.R. Karger and R. Motwani.)

An [math]\displaystyle{ (n,m) }[/math]-safe set instance consists of a universe [math]\displaystyle{ U }[/math] of size [math]\displaystyle{ n }[/math], a safe set [math]\displaystyle{ S\subseteq U }[/math], and [math]\displaystyle{ m }[/math] target sets [math]\displaystyle{ T_1,\dots,T_m\subseteq U }[/math] such that

• [math]\displaystyle{ |S|=|T_1|=\cdots=|T_m| }[/math],
• and, for [math]\displaystyle{ 1\le i\le m, S\cap T_i=\emptyset }[/math].

An isolator for a safe set instance is a set [math]\displaystyle{ I\subseteq U }[/math] that intersects all the target sets but not the safe set. An [math]\displaystyle{ (n,m) }[/math]-universal isolating family [math]\displaystyle{ \mathcal{F} }[/math] is a collection of subsets of [math]\displaystyle{ U }[/math] such that [math]\displaystyle{ \mathcal{F} }[/math] contains an isolator for any [math]\displaystyle{ (n,m) }[/math]-safe set instance. Show that there exists a [math]\displaystyle{ (n,m) }[/math]-universal isolating family [math]\displaystyle{ \mathcal{F} }[/math] such that [math]\displaystyle{ |\mathcal{F}| }[/math] is polynomially bounded in [math]\displaystyle{ n }[/math] and [math]\displaystyle{ m }[/math].

Problem 5

(Due to J. Naor.)

The Chernoff bound is an exponentially decreasing bound on tail distributions. Let [math]\displaystyle{ X_1,\dots,X_n }[/math] be independent random variables and [math]\displaystyle{ \mathbf{E}[X_i]=0 }[/math] for all [math]\displaystyle{ 1\le i\le n }[/math]. Define [math]\displaystyle{ X=X_1+X_2+\dots+X_n }[/math]. We can use the following two kinds of tail inequalities for [math]\displaystyle{ X }[/math].

• Chernoff Bounds:

[math]\displaystyle{ \Pr[|X|\ge\delta]\le\min_{t\ge 0}\frac{\mathbf{E}[e^{t|X|}]}{e^{t\delta}} }[/math].

• [math]\displaystyle{ k }[/math]th-Moment Bound:

[math]\displaystyle{ \Pr[|X|\ge\delta]\le\frac{\mathbf{E}[|X|^k]}{\delta^k} }[/math].

1. Show that for each [math]\displaystyle{ \delta }[/math], there exists a choice of [math]\displaystyle{ k }[/math] such that the [math]\displaystyle{ k }[/math]th-moment bound is stronger than the Chernoff bound. (Hint: You may use the probabilistic method.)
2. Why would we still prefer the Chernoff bound to the seemingly stronger [math]\displaystyle{ k }[/math]th-moment bound?