概率论 (Summer 2013)/Problem Set 3: Difference between revisions
imported>Zhangchihao |
imported>Etone |
||
(9 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
== Problem 1 == | == Problem 1 == | ||
A set of vertices <math>D\subseteq V</math> of graph <math>G(V,E)</math> is a | A set of vertices <math>D\subseteq V</math> of graph <math>G(V,E)</math> is a [http://en.wikipedia.org/wiki/Dominating_set ''dominating set''] if for every <math>v\in V</math>, it holds that <math>v\in D</math> or <math>v</math> is adjacent to a vertex in <math>D</math>. The problem of computing minimum dominating set is NP-hard. | ||
* Prove that for every <math>d</math>-regular graph with <math>n</math> vertices, there exists a dominating set with size at most <math>\frac{n(1+\ln(d+1))}{d+1}</math>. | * Prove that for every <math>d</math>-regular graph with <math>n</math> vertices, there exists a dominating set with size at most <math>\frac{n(1+\ln(d+1))}{d+1}</math>. | ||
* Try to obtain an upper bound for dominating set using | * 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 == | == Problem 2 == | ||
Line 13: | Line 13: | ||
== Problem 3 == | == Problem 3 == | ||
Let <math>G(V,E)</math> be a cycle of length <math>4n</math> and let <math>V=V_1\cup V_2\cup\dots V_n</math> be a partition of its <math>4n</math> vertices into <math>n</math> pairwise disjoint subsets, each of cardinality 4. Is it true that there must be an independent set of <math>G</math> containing precisely one vertex from each <math>V_i</math>? (Prove or supply a counter example.) | |||
Hint: you can use Lovász Local Lemma. | |||
== Problem 4 == | == Problem 4 == | ||
(Due to D.R. Karger and R. Motwani.) | |||
An <math>(n,m)</math>-safe set instance consists of a universe <math>U</math> of size <math>n</math>, a safe set <math>S\subseteq U</math>, and <math>m</math> target sets <math>T_1,\dots,T_m\subseteq U</math> such that | |||
* <math>|S|=|T_1|=\cdots=|T_m|</math>, | |||
* and, for <math>1\le i\le m, S\cap T_i=\emptyset</math>. | |||
An <i>isolator</i> for a safe set instance is a set <math>I\subseteq U</math> that intersects all the target sets but not the safe set. An <i><math>(n,m)</math>-universal isolating family <math>\mathcal{F}</math></i> is a collection of subsets of <math>U</math> such that <math>\mathcal{F}</math> contains an isolator for any <math>(n,m)</math>-safe set instance. Show that there exists a <math>(n,m)</math>-universal isolating family <math>\mathcal{F}</math> such that <math>|\mathcal{F}|</math> is polynomially bounded in <math>n</math> and <math>m</math>. | |||
== Problem 5 == | == Problem 5 == | ||
(Due to J. Naor.) | |||
The <i>Chernoff bound</i> is an exponentially decreasing bound on tail distributions. Let <math>X_1,\dots,X_n</math> be independent random variables and <math>\mathbf{E}[X_i]=0</math> for all <math>1\le i\le n</math>. Define <math>X=X_1+X_2+\dots+X_n</math>. We can use the following two kinds of tail inequalities for <math>X</math>. | |||
* '''Chernoff Bounds:''' | |||
:<math>\Pr[|X|\ge\delta]\le\min_{t\ge 0}\frac{\mathbf{E}[e^{t|X|}]}{e^{t\delta}}</math>. | |||
* '''<math>k</math>th-Moment Bound: | |||
:<math>\Pr[|X|\ge\delta]\le\frac{\mathbf{E}[|X|^k]}{\delta^k}</math>. | |||
# Show that for each <math>\delta</math>, there exists a choice of <math>k</math> such that the <math>k</math>th-moment bound is stronger than the Chernoff bound. (Hint: You may use the probabilistic method.) | |||
# Why would we still prefer the Chernoff bound to the seemingly stronger <math>k</math>th-moment bound? |
Latest revision as of 04:44, 23 July 2013
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].
- 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.)
- Why would we still prefer the Chernoff bound to the seemingly stronger [math]\displaystyle{ k }[/math]th-moment bound?