imported>Haimin |
imported>Haimin |
| Line 1: |
Line 1: |
| <font color="red" size=5>Under Construction</font>
| |
|
| |
|
| == Problem 1 ==
| |
| Let <math>L = L(K_{m,n})</math> be the laplacian matrix of the complete bipartite graph <math>K_{mn}</math>.
| |
| * Find a simple upper bound on rank<math>(L - nI)</math>. Deduce a lower bound on the number of eigenvalues of <math>L</math> equal to <math>n</math>.
| |
| * Assume <math>m\neq n</math>, and do the same as (a) for <math>m</math> instead of <math>n</math>.
| |
| * Find the remaining eigenvalues of <math>L</math>.
| |
| * Compute <math>\kappa\left(K_{m,n}\right)</math>, the number of spanning trees of <math>K_{m,n}</math>.
| |
| * Give a combinatorial proof of the formula for <math>\kappa\left(K_{m,n}\right)</math>.
| |
|
| |
| == Problem 2 ==
| |
| (Erdős-Spencer 1974)
| |
|
| |
| 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.
| |
|
| |
| 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>.
| |
|
| |
| * 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.
| |
| * 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>. (This gives a lower bound for the number of weighings required to determine the weights of <math>n</math> coins.)
| |
|
| |
| == 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 ==
| |
|
| |
| * Prove there is a 2-coloring of edges of <math>K_n</math> with at most <math>\binom{n}{k}2^{1-\binom{a}{2}}</math> monochromatic <math>K_a</math>.
| |
| * Prove there is a 2-coloring of edges of the complete bipartite graph <math>K_{m,n}</math> with at most <math>\binom{m}{a}\binom{n}{b}2^{1-ab}+\binom{n}{a}\binom{m}{b}2^{1-ab}</math> monochromatic <math>K_{a,b}</math>.
| |
|
| |
| == Problem 5 ==
| |
| 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>.
| |