imported>Zhangchihao |
imported>Zhangchihao |
| 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 at least one of its neighbour is in <math>D</math>. The problem of computing minimum dominating set is NP-hard.
| | Let <math>X_1,X_2,\dots,X_n</math> be independent geometrically distributed random variables each having expectation 2 (each of the <math>X_i</math> is an independent experiment counting the number of tosses of an unbiased coin up to and including the first HEADS). Let <math>X=\sum_{i=1}^nX_i</math> and <math>\delta</math> be a positive real constant. Derive the best upper bound you can on <math>\Pr[X>(1+\delta)(2n)]</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 the size of dominating set using Lovász Local Lemma. Is it better or worse than previous one? Why?
| |
|
| |
|
| == Problem 2 == | | == Problem 2 == |
| 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>.
| |
|
| |
| 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>.
| |
|
| |
| == 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 ==
| |