随机算法 (Spring 2014)/Problem Set 4 and 组合数学 (Spring 2014)/Problem Set 4: 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 ==
A proper <math>q</math>-coloring of a graph <math>G(V,E)</math> is a mapping <math>f:V\to [q]</math> such that for any edge <math>uv\in E</math> we have <math>f(u)\neq f(v)</math>.
An <math>n</math>-player tournament (竞赛图) <math>T([n],E)</math> is said to be '''transitive''', if there exists a permutation <math>\pi</math> of <math>[n]</math> such that <math>\pi_i<\pi_j</math> for every <math>(i,j)\in E</math>.


Consider the following Markov chain for proper <math>q</math>-colorings of a graph <math>G(V,E)</math>:
Show that for any <math>k\ge 3</math>, there exists an <math>N(k)</math> such that every tournament of <math>n\ge N(k)</math> players contains a transitive sub-tournament of <math>k</math> players.
{{Theorem|Markov Chain for Graph Coloring|
:Start with a proper <math>q</math>-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:
== Problem 2 ==
# ergodic (i.e., aperiodic);
Let <math>G(U,V,E)</math> be a bipartite graph. Let <math>\delta_U</math> be the '''minimum''' degree of vertices in <math>U</math>, and <math>\Delta_V</math> be the maximum degree of vertices in <math>V</math>.
# irreducible if <math>q\ge \Delta+2</math>;
# with uniform stationary distribution.


== Problem 2 ==
Show that if <math>\delta_U\ge \Delta_V</math>, then there must be a matching in <math>G</math> such that all vertices in <math>U</math> are matched.
Let <math>G(V,E)</math> be an undirected graph with known maximum degree <math>\Delta</math>. You want to design random walks over the vertices in <math>V</math> such that at each step only adjacent vertices are allowed to walk to (i.e., the transition matrix <math>P</math> is defined on <math>V\times V</math> and <math>P(u,v)>0</math> only if <math>uv\in E</math>). You are allowed to design your transition matrix to achieve different stationary distributions.
* Suppose that <math>G</math> is not necessarily regular (every vertex has the same degree). Design a time-reversible lazy random walk which is ergodic and always converges to uniform stationary distribution.
* Given an arbitrary distribution <math>\pi</math> over <math>V</math>, design a time-reversible lazy random walk which is ergodic and always converges to the stationary distribution <math>\pi</math>.
* (bonus question) Try to give sufficient conditions in terms of <math>G</math> and <math>\pi</math> for the rapid mixing of the above two random walks.


== Problem 3 ==
== Problem 3 ==
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>.
Prove the following statement:
* 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.
* For any <math>n</math> distinct finite sets <math>S_1,S_2,\ldots,S_n</math>, there always is a collection <math>\mathcal{F}\subseteq \{S_1,S_2,\ldots,S_n\}</math> such that <math>|\mathcal{F}|\ge \lfloor\sqrt{n}\rfloor</math> and for any different <math>A,B,C\in\mathcal{F}</math> we have <math>A\cup B\neq C</math>.
* 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.
 
* 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>.
(Hint: use Dilworth theorem.)
* Suppose that the maximum degree of <math>G</math> is known but the graph is not necessarily regular. Design a random walk on <math>G</math> 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 4==
A Boolean matrix is a matrix whose entries are either 0 or 1. We call a matrix '''1-matrix''' if all its entries are 1.
Let <math>A</math> be a Boolean matrix satisfying:
* there are totally <math>m</math> 1-entries in <math>A</math>;
* every row of <math>A</math> contains at most <math>s</math> 1-entries;
* <math>A</math> does not contain any <math>r\times r</math> 1-matrix as submatrix.
Use König-Egerváry Theorem to prove: we need at least <math>\frac{m}{sr}</math> many 1-matrices to precisely cover all the 1-entries in <math>A</math>.

Revision as of 09:13, 4 June 2014

Problem 1

An [math]\displaystyle{ n }[/math]-player tournament (竞赛图) [math]\displaystyle{ T([n],E) }[/math] is said to be transitive, if there exists a permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [n] }[/math] such that [math]\displaystyle{ \pi_i\lt \pi_j }[/math] for every [math]\displaystyle{ (i,j)\in E }[/math].

Show that for any [math]\displaystyle{ k\ge 3 }[/math], there exists an [math]\displaystyle{ N(k) }[/math] such that every tournament of [math]\displaystyle{ n\ge N(k) }[/math] players contains a transitive sub-tournament of [math]\displaystyle{ k }[/math] players.

Problem 2

Let [math]\displaystyle{ G(U,V,E) }[/math] be a bipartite graph. Let [math]\displaystyle{ \delta_U }[/math] be the minimum degree of vertices in [math]\displaystyle{ U }[/math], and [math]\displaystyle{ \Delta_V }[/math] be the maximum degree of vertices in [math]\displaystyle{ V }[/math].

Show that if [math]\displaystyle{ \delta_U\ge \Delta_V }[/math], then there must be a matching in [math]\displaystyle{ G }[/math] such that all vertices in [math]\displaystyle{ U }[/math] are matched.

Problem 3

Prove the following statement:

  • For any [math]\displaystyle{ n }[/math] distinct finite sets [math]\displaystyle{ S_1,S_2,\ldots,S_n }[/math], there always is a collection [math]\displaystyle{ \mathcal{F}\subseteq \{S_1,S_2,\ldots,S_n\} }[/math] such that [math]\displaystyle{ |\mathcal{F}|\ge \lfloor\sqrt{n}\rfloor }[/math] and for any different [math]\displaystyle{ A,B,C\in\mathcal{F} }[/math] we have [math]\displaystyle{ A\cup B\neq C }[/math].

(Hint: use Dilworth theorem.)

Problem 4

A Boolean matrix is a matrix whose entries are either 0 or 1. We call a matrix 1-matrix if all its entries are 1.

Let [math]\displaystyle{ A }[/math] be a Boolean matrix satisfying:

  • there are totally [math]\displaystyle{ m }[/math] 1-entries in [math]\displaystyle{ A }[/math];
  • every row of [math]\displaystyle{ A }[/math] contains at most [math]\displaystyle{ s }[/math] 1-entries;
  • [math]\displaystyle{ A }[/math] does not contain any [math]\displaystyle{ r\times r }[/math] 1-matrix as submatrix.

Use König-Egerváry Theorem to prove: we need at least [math]\displaystyle{ \frac{m}{sr} }[/math] many 1-matrices to precisely cover all the 1-entries in [math]\displaystyle{ A }[/math].

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