**Academic Integrity**plz.

Try Firefox if your web browser (e.g. Chrome, IE) does not support MathML, a part of HTML5.

# Combinatorics: Problem Set 3

## 1 Problem 1

### 1.1

By assigning each coin a distinct integer in $[1,n]$, we can construct a bijection from the weights of different coins to a subset of $[n]$. Recall that weight of each coin is $0$ or $1$. For some specific coin which is assigned number $i$, weights of $0$ means $i\notin T$, weights of $1$ means $i\in T$. Thus the weights of $n$ coins is mapped to a subset of $[n]$. Note that the mapping is reversible. Therefore this is a bijection.

Given $n$ coins. If there is a determing collection ${S}_{1},{S}_{2},\mathrm{\cdots},{S}_{m}\subseteq [n]$, we can calculate the $m$ cardinalities by weighing the the coins in ${S}_{i}$. Since $T$ can be determined by the $m$ values, the weights of the $n$ coins can also be determined due to the bijection.

### 1.2

The cardinalities $|{S}_{i}\cap T|$ must be an integer in $[0,n]$, all the $m$ cardinalites of intersections have at most ${(n+1)}^{m}$ distinct results. One result of interections can determine at most one subset. Due to the definition of determining and the pigeonhole principle, we have

$${(n+1)}^{m}\ge {2}^{n},$$ |

i.e.

$$m\ge \frac{n}{{\mathrm{log}}_{2}(n+1)}.$$ |

## 2 Problem 2

### 2.1

Let $S$ be a set of vertices constructed by randomly including vertex with probability $p$ ($p$ to be determined). Let $Y$ be set of vertices which is neither included in $S$ nor adjacent with a vertex in $S$. Clearly, $S\cup Y$ is a dominating set. By the linearity of expectation,

$?[|S\cup Y|]$ | $=?[|S|]+?[|Y|]$ | ||

$={\displaystyle \sum _{v\in V}}\mathrm{Pr}[v\in S]+{\displaystyle \sum _{v\in V}}\mathrm{Pr}[v\notin V\wedge d\text{neighbors of}v\in V]$ | |||

$=np+n{(1\u2013p)}^{d+1}.$ |

Let $f(p)=p+{(1\u2013p)}^{d+1}$, solve ${f}^{\prime}(p)=0$ we get $p=1\u2013{(d+1)}^{\u20131/d}$. Let $g(d)=f(p)\u2013(1+\mathrm{ln}(d+1))/(d+1)$,

$g(d)$ | $=1\u2013{(d+1)}^{\u20131/d}+{(d+1)}^{\u2013(d+1)/d}\u2013{\displaystyle \frac{1+\mathrm{ln}(d+1)}{d+1}}$ | ||

${g}^{\prime}(d)$ | $={(d+1)}^{\u20131/d\u20132}(d({(d+1)}^{1/d}\u20131)\u20131)\mathrm{ln}(d+1)/d.$ |

Note that $$, ${g}^{\prime}(d)\ge 0$ when $d\ge 1$, ${lim}_{d\to +\mathrm{\infty}}g(d)=0$. Thus $f(p)\le n(1+\mathrm{ln}(d+1))/(d+1)$ when $d\ge 1$,

$?[|S\cup Y|]=n\times f(p)\le {\displaystyle \frac{n(1+\mathrm{ln}(d+1))}{d+1}},$ |

i.e. there exists a dominating set with size at most $\frac{n(1+\mathrm{ln}(d+1))}{d+1}$.

### 2.2

Uniformly sample $m$ points as set $S$. For each vertex $i$, we define event ${A}_{i}$ as vertex $i$ is neither included in $S$ nor adjacent with any vertex in $S$. Clearly $\forall i\in V,\mathrm{Pr}[{A}_{i}]=\left({\scriptscriptstyle \begin{array}{c}n\u2013d\u20131\\ m\end{array}}\right)/\left({\scriptscriptstyle \begin{array}{c}n\\ m\end{array}}\right)\le {(1\u2013m/n)}^{d+1}$, and all the $n$ events depend on other $n\u20131$ events. By the Lovász Local Lemma, if we make sure

$$e{(1\u2013m/n)}^{d+1}n\le 1,$$ |

there exists a dominating set with size at most $m$. In another word,

$$m\ge n(1\u2013{(en)}^{\u20131/(d+1)}).$$ |

To compare the two bounds, assuming the new bound is better than previous one, we have

$1\u2013{(en)}^{\u20131/(d+1)}\le (1+\mathrm{ln}(d+1))/(d+1)$ | |||

$\iff $ | $d+1\ge (d\u2013\mathrm{ln}(d+1)){(en)}^{1/(d+1)}$ | ||

$\iff $ | $n\le {\displaystyle \frac{1}{e}}{({\displaystyle \frac{d+1}{d\u2013\mathrm{ln}(d+1)}})}^{\u20131/(d+1)}.$ |

Let $f(d)={(\frac{d+1}{d\u2013\mathrm{ln}(d+1)})}^{\u20131/(d+1)}$. Note that ${lim}_{d\to 0}f(d)=0$; ${f}^{\prime}(d)\ge 0$ when $d\ge 0$; ${lim}_{d\to +\mathrm{\infty}}f(d)=1$, $n$ must be less than $1/e$ to make the new bound lower than the old bound. This is impossible. Therefore the new bound is worse than previous one.

## 3 Problem 3

Any edge $k$-coloring for ${K}_{n}$ forms a partition of ${K}_{n}$. Any part of the partition is an edge-induced subgraph of ${K}_{n}$. The only way we know to avoid $H$ is to make sure any subgraph is a subgraph of $G$ or a subgraph of some graph which is isomorphic to $G$.

Here comes a randomized iterative coloring scheme. In the beginning, all the $\left({\scriptscriptstyle \begin{array}{c}n\\ 2\end{array}}\right)$ edges have not colored. During each iteration, we uniformly rearrange the label of the $n$ vertices at random, and choose a new color for this iteration. For any two vertice which are labelled $i$ and $j$, if the edge $(i,j)$ has not colored yet and there is an edge $(i,j)$ in $G$, we color the edge with the color for this iteration.

Clearly any monochromatic subgraph of ${K}_{n}$ will be a edge-induced subgraph of some graph which is isomorphic to $G$, thus ${K}_{n}$ will not contain monochromatic $H$. For each iteration, any edge which has not colored will be colored with probability $m/\left({\scriptscriptstyle \begin{array}{c}n\\ 2\end{array}}\right)$. Hence

$\mathrm{Pr}[\exists \text{an edge which survives after}k\text{times iteration}]$ | $\le \left({\displaystyle \begin{array}{c}n\\ 2\end{array}}\right)\mathrm{Pr}[\text{some fixed edge survives after}k\text{times iteration}]$ | ||

$={\displaystyle \frac{n(n\u20131)}{2}}{(1\u2013{\displaystyle \frac{2m}{n(n\u20131)}})}^{k}$ | |||

$$ | |||

$\le {\displaystyle \frac{n(n\u20131)}{2}}\mathrm{exp}(\u20132\mathrm{ln}n)$ | |||

$={\displaystyle \frac{n(n\u20131)}{2}}{\displaystyle \frac{1}{{n}^{2}}}$ | |||

$$ |

Thus all the edge is colored after $k$ times iteration with probability at least $1\u20131/2=1/2$. Therefore there is an edge $k$-coloring for ${K}_{n}$ that ${K}_{n}$ contains no monochromatic $H$.

## 4 Problem 4

For each subset ${V}_{i}$ we uniformly sample a vertex at random. For each $(a,b)\in E$, if $\mathrm{\nexists}{V}_{i}$ s.t. $a\in {V}_{i}\wedge b\in {V}_{i}$, we define a bad event ${A}_{(a,b)}$ denotes that vertices $a$ and $b$ are sampled so that it fails to sample an independent set of $G$ which contains precisely one vertex from each ${V}_{i}$. Clearly, the mapping between the edges connect different subsets and bad events is bijection.

Any bad event ${A}_{(a,b)}$ depends on the bad events which have at least a vertex which is in the subset which contains $a$ or $b$. Since the graph is a cycle, every vertex has degree of $2$. For all $i\in \{1,2,\mathrm{\cdots},n\}$, the $k$ vertices in ${V}_{i}$ is involved in at most $2k$ bad events. Thus a bad event depends on at most $2*(2k\u20131)$ events.

Since any bad event happens with probability $1/{k}^{2}$, by the Lovász Local Lemma,

$$ |

all bad events does not happen with probablity greater than $0$, i.e. there exists an independent set of G containing precisely one vertex from each ${V}_{i}$.

## 5 Problem 5

Independently assign each vertex $0$ or $1$ with probablity $1/2$ at random. $\forall i\in \mathscr{H}$, define event ${A}_{i}$ as all vertices $v\in i$ is assigned same number. Clearly, $\forall i\in \mathscr{H},\mathrm{Pr}[{A}_{i}]=2\times {2}^{\u2013k}={2}^{1\u2013k}$. For any hyperedge $i$, $i$ shares vertex with at most ${k}^{2}$ hyperedges. This implies the maximum degree of the dependency graph for the events ${A}_{1},{A}_{2},\mathrm{\cdots},{A}_{|\mathscr{H}|}$ is at most ${k}^{2}$. Since

$$e{2}^{1\u2013k}({k}^{2}+1)$$ |

is monotonic decreasing when $k>3$, and the value of above expression is less than $1$ when $k\ge 10$. Due to the Lovász Local Lemma, $\mathrm{Pr}[\wedge \overline{{A}_{i}}]>0$, i.e. there is a $2$-coloring $f:V\to \{0,1\}$ s.t. $\mathscr{H}$ does not contain any monochromatic hyperedge $S\in \mathscr{H}$.

Combin.PS3 by himemeizhi is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.