组合数学 (Fall 2019)/Problem Set 3

Under Construction

Problem 1

Let $L=L(K_{m,n})$ be the laplacian matrix of the complete bipartite graph $K_{mn}$.

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

Problem 2

(Erdős-Spencer 1974)

Let $n$ 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 $S_1,S_1,\dots ,S_m\subseteq [n]$ is called determining if an arbitrary subset $T\subseteq [n]$ can be uniquely determined by the cardinalities $|S_i\cap T|,1\le i\le m$.

• Prove that if there is a determining collection $S_1,S_1,\dots ,S_m\subseteq [n]$, then there is a way to determine the weights of $n$ coins with $m$ weighings.
• Use pigeonhole principle to show that if a collection $S_1,S_1,\dots ,S_m\subseteq [n]$ is determining, then it must hold that $m\ge \frac{n}{{\log }_2(n+1)}$. (This gives a lower bound for the number of weighings required to determine the weights of $n$ coins.)

Problem 3

A set of vertices $D\subseteq V$ of graph $G(V,E)$ is a dominating set if for every $v\in V$, it holds that $v\in D$ or $v$ is adjacent to a vertex in $D$. The problem of computing minimum dominating set is NP-hard.

• Prove that for every $d$-regular graph with $n$ vertices, there exists a dominating set with size at most $\frac{n(1+\ln (d+1))}{d+1}$.

• 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 $K_n$ with at most $(\genfrac{}{}{0ex}{}{n}{k})2^{1-(\genfrac{}{}{0ex}{}{a}{2})}$ monochromatic $K_a$.
• Prove there is a 2-coloring of edges of the complete bipartite graph $K_{m,n}$ with at most $(\genfrac{}{}{0ex}{}{m}{a})(\genfrac{}{}{0ex}{}{n}{b})2^{1-ab}+(\genfrac{}{}{0ex}{}{n}{a})(\genfrac{}{}{0ex}{}{m}{b})2^{1-ab}$ monochromatic $K_{a,b}$.

Problem 5

Let $H(W,F)$ be a graph and $n>|W|$ be an integer. It is known that for some graph $G(V,E)$ such that $|V|=n$, $|E|=m$, $G$ does not contain $H$ as a subgraph. Prove that for $k>\frac{n^2\ln n}{m}$, there is an edge $k$-coloring for $K_n$ that $K_n$ contains no monochromatic $H$.

Remark: Let $E=(\genfrac{}{}{0ex}{}{V}{2})$ be the edge set of $K_n$. "An edge $k$-coloring for $K_n$" is a mapping $f:E\to [k]$.