概率论 (Summer 2013)/Problem Set 3: Difference between revisions
imported>Zhangchihao |
imported>Zhangchihao |
||
| (2 intermediate revisions by the same user 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 <i>dominating set</i> if for every <math>v\in V</math>, either <math>v\in D</math> or one of its neighbour is 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>. | A set of vertices <math>D\subseteq V</math> of graph <math>G(V,E)</math> is a <i>dominating set</i> if for every <math>v\in V</math>, either <math>v\in D</math> or one of its neighbour is 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>. | |||
* 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 9: | 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 == | ||
== Problem 5 == | == Problem 5 == | ||
Revision as of 17:00, 18 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], either [math]\displaystyle{ v\in D }[/math] or one of its neighbour is 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.