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

Under Construction

Problem 1

Let [math]\displaystyle{ L = L(K_{m,n}) }[/math] be the laplacian matrix of the complete bipartite graph [math]\displaystyle{ K_{mn} }[/math].

• Find a simple upper bound on rank[math]\displaystyle{ (L - nI) }[/math]. Deduce a lower bound on the number of eigenvalues of $L$ equal to $n$.
• Assume [math]\displaystyle{ m\neq n }[/math], and do the same as (a) for [math]\displaystyle{ m }[/math] instead of [math]\displaystyle{ n }[/math].
• Find the remaining eigenvalues of [math]\displaystyle{ L }[/math].
• Compute [math]\displaystyle{ \kappa\left(K_{m,n}\right) }[/math], the number of spanning trees of [math]\displaystyle{ K_{m,n} }[/math].
• Give a combinatorial proof of the formula for [math]\displaystyle{ \kappa\left(K_{m,n}\right) }[/math].

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

• Prove there is a 2-coloring of edges of [math]\displaystyle{ K_n }[/math] with at most [math]\displaystyle{ \binom{n}{k}2^{1-\binom{a}{2}} }[/math] monochromatic [math]\displaystyle{ K_a }[/math].
• Prove there is a 2-coloring of edges of the complete bipartite graph [math]\displaystyle{ K_{m,n} }[/math] with at most [math]\displaystyle{ \binom{m}{a}\binom{n}{b}2^{1-ab}+\binom{n}{a}\binom{m}{b}2^{1-ab} }[/math] monochromatic [math]\displaystyle{ K_{a,b} }[/math].

Problem 5

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].