计算复杂性 (Fall 2019)/作业4已提交名单

Problem 1

Let [math]\displaystyle{ L(n,m) }[/math] be the maximum length of sequence with the following properties: the sum of every [math]\displaystyle{ n }[/math] consecutive elements is negative, the sum of every [math]\displaystyle{ m }[/math] consecutive elements is positive.

• (easy) Prove [math]\displaystyle{ L(n,m)\lt mn }[/math].
• (nontrivial) You do not need to solve both (1.) and (2.), choose one among the two. But feel free to submit solutions for both.

1. Prove [math]\displaystyle{ L(n,m)\lt m+n-1 }[/math].
2. Prove [math]\displaystyle{ L(n,m)\geq m+n-2 }[/math] for any [math]\displaystyle{ gcd(n,m)=1 }[/math].

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

"An edge [math]\displaystyle{ k }[/math]-coloring for [math]\displaystyle{ G(V,E) }[/math]" is a mapping [math]\displaystyle{ f:E\to[k] }[/math], where [math]\displaystyle{ E }[/math] is the edge set[math]\displaystyle{ E }[/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].

Problem 7.1

You do not need to solve both (7.1) and (7.2), choose one among the two. But feel free to submit solutions for both.

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: "An edge [math]\displaystyle{ k }[/math]-coloring for [math]\displaystyle{ G(V,E) }[/math]" is a mapping [math]\displaystyle{ f:E\to[k] }[/math], where [math]\displaystyle{ E }[/math] is the edge set [math]\displaystyle{ E }[/math].

Problem 7.2

You do not need to solve both (7.1) and (7.2), choose one among the two. But feel free to submit solutions for both.

Consider the family of all pairs [math]\displaystyle{ (A, B) }[/math] of disjoint [math]\displaystyle{ k }[/math] element subsets of [math]\displaystyle{ \{1,...,n\} }[/math]. A set [math]\displaystyle{ Y }[/math] separates the pair [math]\displaystyle{ (A, B) }[/math] if [math]\displaystyle{ A\subseteq Y }[/math] and [math]\displaystyle{ B\cap Y=\phi }[/math]. Prove that there exist [math]\displaystyle{ \ell=2k4^k\ln n }[/math] sets such that every pair [math]\displaystyle{ (A, B) }[/math] is separated by at least one of them.