随机算法 (Spring 2013)/Problem Set 4 and 组合数学 (Spring 2014)/Problem Set 2: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
 
imported>Etone
 
Line 1: Line 1:
== Problem 1 ==
== Problem 1==
Consider the Markov chain of graph coloring
Prove the following identity:  
{{Theorem|Markov Chain for Graph Coloring|
*<math>\sum_{k=1}^n k{n\choose k}= n2^{n-1}</math>.
:Start with a proper coloring of <math>G(V,E)</math>. At each step:
# Pick a vertex <math>v\in V</math> and a color <math>c\in[q]</math> uniformly at random.
# Change the color of <math>v</math> to <math>c</math> if the resulting coloring is proper; do nothing if otherwise.
}}


Show that the Markov chain is:
(Hint: Use double counting.)
# aperiodic;
# irreducible if <math>q\ge \Delta+2</math>;
# with uniform stationary distribution.


== Problem 2 ==
== Problem 2 ==
Consider the following random walk on hypercube:
(Erdős-Spencer 1974)
{{Theorem|Yet another random Walk on Hypercube|
: At each step, for the current state <math>x\in\{0,1\}^n</math>:
# pick an <math>i\in\{0,1,2,\ldots,n\}</math> uniformly at random;
# flip <math>x_i</math> (let <math>x_i=1-x_i</math>) if <math>i\neq 0</math>.
}}
* Show that the random walk is ergodic.
* Give the stationary distribution of the random walk.
* Analyze the mixing time of the random walk by coupling.


Hint.1: Construct a coupling rule such that the Hamming distance between two states never increases.
Let <math>n</math> coins of weights 0 and 1 be given. We are also given a scale with which we may weigh any subset of the coins. Our goal is to determine the weights of coins (that is, to known which coins are 0 and which are 1) with the minimal number of weighings.  


Hint.2: When constructing the coupling, consider a cyclic permutation of disagreeing positions.
This problem can be formalized as follows: A collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math> is called '''determining''' if an arbitrary subset <math>T\subseteq[n]</math> can be uniquely determined by the cardinalities <math>|S_i\cap T|, 1\le i\le m</math>.


== Problem 3==
* Prove that if there is a determining collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math>, then there is a way to determine the weights of <math>n</math> coins with <math>m</math> weighings.
Consider the following random walk over all subsets <math>S\in{[n]\choose k}</math> for some <math>k\le \frac{n}{2}</math>:
* Use pigeonhole principle to show that if a collection <math>S_1,S_1,\ldots,S_m\subseteq [n]</math> is determining, then it must hold that <math>m\ge \frac{n}{\log_2(n+1)}</math>.
{{Theorem|Random walk over <math>k</math>-subsets|
: At each step, for the current state <math>S\in{[n]\choose k}</math>:
# with probability <math>p</math>, do nothing;
# else pick an <math>x\in S</math> and a <math>y\in[n]\setminus S</math> independently and uniformly at random, and change the current set to be <math>S\setminus\{x\}\cup\{y\}</math>.
}}
You are allowed to choose a self-loop probability <math>p</math> for your convenience.
* Show that the random walk is ergodic
* Give the stationary distribution of the random walk.
* Prove that the mixing time is <math>O(k\log k)</math> by coupling.


Hint.1: Considering a coupling <math>(S,T)</math>, the <math>[n]</math> is partitioned into <math>S\cap T,S\setminus T,T\setminus S,\overline{S\cup T}</math>. Design a coupling rule to adopt different cases (of where <math>x</math> and <math>y</math> belong) so that the difference between two states never increases.
(This gives a lower bound for the number of weighings required to determine the weights of <math>n</math> coins.)


Hint.2: Use a cyclic permutation (with some desirable property) of elements in <math>S\triangle T</math> which is the symmetric difference between <math>S</math> and <math>T</math>.
 
== Problem 3 ==
 
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>.
 
* 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?


== Problem 4 ==
== Problem 4 ==
Let <math>G(V,E)</math> be a connected undirected simple graph (no self-loops and parallel edges) defined on <math>n</math> vertices. Let <math>\phi(G)</math> be the expansion ratio of <math>G</math>. <math>G</math> is NOT necessarily regular. For any <math>v\in V</math>, let <math>d_v</math> be the degree of vertex <math>v</math>.
Let <math>H(W,F)</math> be a graph and <math>n>|W|</math> be an integer. It is known that for some graph <math>G(V,E)</math> such that <math>|V|=n</math>, <math>|E|=m</math>, <math>G</math> does not contain <math>H</math> as a subgraph. Prove that for <math>k>\frac{n^2\ln n}{m}</math>, there is an edge <math>k</math>-coloring for <math>K_n</math> that <math>K_n</math> contains no monochromatic <math>H</math>.
* What is the largest possible value for <math>\phi(G)</math>? Construct a graph <math>G</math> with this expansion ratio and explain why it is the largest.
 
* What is the smallest possible value for <math>\phi(G)</math>? Construct a graph <math>G</math> with this expansion ratio and explain why it is the smallest.
Remark: Let <math>E=\binom{V}{2}</math> be the edge set of <math>K_n</math>. "An edge <math>k</math>-coloring for <math>K_n</math>" is a mapping <math>f:E\to[k]</math>.
* Run a lazy random walk on <math>G</math>. What is the stationary distribution? Starting from an arbitrary vertex in an arbitrary unknown <math>G</math>, how long in the worst case should you run the random walk to guarantee the distribution of the current position is within a total variation distance of <math>\epsilon</math> from the stationary distribution? Give an upper bound of the time in terms of <math>n</math> and <math>\epsilon</math>.
 
* Suppose that the maximum degree of <math>G</math> is known but the graph is not necessarily regular. Design a random walk with uniform stationary distribution. How long should you run the random walk to be within <math>\epsilon</math>-close to the uniform distribution in the worst case?
== Problem 5 ==
 
Let <math>G(V,E)</math> be a cycle of length <math>k\cdot n</math> and let <math>V=V_1\cup V_2\cup\dots V_n</math> be a partition of its <math>k\cdot n</math> vertices into <math>n</math> pairwise disjoint subsets, each of cardinality <math>k</math>.  
For <math>k\ge 11</math>, show that there must be an independent set of <math>G</math> containing precisely one vertex from each <math>V_i</math>.
 
Hint: you can use Lovász Local Lemma.

Revision as of 11:26, 9 April 2014

Problem 1

Prove the following identity:

  • [math]\displaystyle{ \sum_{k=1}^n k{n\choose k}= n2^{n-1} }[/math].

(Hint: Use double counting.)

Problem 2

(Erdős-Spencer 1974)

Let [math]\displaystyle{ n }[/math] coins of weights 0 and 1 be given. We are also given a scale with which we may weigh any subset of the coins. Our goal is to determine the weights of coins (that is, to known which coins are 0 and which are 1) with the minimal number of weighings.

This problem can be formalized as follows: A collection [math]\displaystyle{ S_1,S_1,\ldots,S_m\subseteq [n] }[/math] is called determining if an arbitrary subset [math]\displaystyle{ T\subseteq[n] }[/math] can be uniquely determined by the cardinalities [math]\displaystyle{ |S_i\cap T|, 1\le i\le m }[/math].

  • Prove that if there is a determining collection [math]\displaystyle{ S_1,S_1,\ldots,S_m\subseteq [n] }[/math], then there is a way to determine the weights of [math]\displaystyle{ n }[/math] coins with [math]\displaystyle{ m }[/math] weighings.
  • Use pigeonhole principle to show that if a collection [math]\displaystyle{ S_1,S_1,\ldots,S_m\subseteq [n] }[/math] is determining, then it must hold that [math]\displaystyle{ m\ge \frac{n}{\log_2(n+1)} }[/math].

(This gives a lower bound for the number of weighings required to determine the weights of [math]\displaystyle{ n }[/math] coins.)


Problem 3

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?

Problem 4

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 5

Let [math]\displaystyle{ G(V,E) }[/math] be a cycle of length [math]\displaystyle{ k\cdot n }[/math] and let [math]\displaystyle{ V=V_1\cup V_2\cup\dots V_n }[/math] be a partition of its [math]\displaystyle{ k\cdot n }[/math] vertices into [math]\displaystyle{ n }[/math] pairwise disjoint subsets, each of cardinality [math]\displaystyle{ k }[/math]. For [math]\displaystyle{ k\ge 11 }[/math], show that there must be an independent set of [math]\displaystyle{ G }[/math] containing precisely one vertex from each [math]\displaystyle{ V_i }[/math].

Hint: you can use Lovász Local Lemma.

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Spring_2013)/Problem_Set_4&oldid=6026"