# Combin.PS3

My Solution for Combinatorics for the Fall 2015 semester, Problem Set 3. Keep your Academic Integrity plz.

# Combinatorics: Problem Set 3

Himemiya

## 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},\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}\geq 2^{n},$

i.e.

 $m\geq\frac{n}{\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,

 $\displaystyle\mathbf{E}[|S\cup Y|]$ $\displaystyle=\mathbf{E}[|S|]+\mathbf{E}[|Y|]$ $\displaystyle=\sum_{v\in V}\Pr[v\in S]+\sum_{v\in V}\Pr[v\notin V\land\text{d% neighbors of v}\in V]$ $\displaystyle=np+n(1-p)^{d+1}.$

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

 $\displaystyle g(d)$ $\displaystyle=1-(d+1)^{-1/d}+(d+1)^{-(d+1)/d}-\frac{1+\ln(d+1)}{d+1}$ $\displaystyle g^{\prime}(d)$ $\displaystyle=(d+1)^{-1/d-2}(d((d+1)^{1/d}-1)-1)\ln(d+1)/d.$

Note that $g(1)=1/4-\ln(2)/2<0$, $g^{\prime}(d)\geq 0$ when $d\geq 1$, $\lim_{d\to+\infty}g(d)=0$. Thus $f(p)\leq n(1+\ln(d+1))/(d+1)$ when $d\geq 1$,

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

i.e. there exists a dominating set with size at most $\frac{n(1+\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,\Pr[A_{i}]={\left({{n-d-1}\atop{m}}\right)}/{\left({{n}\atop{m}% }\right)}\leq(1-m/n)^{d+1}$, and all the $n$ events depend on other $n-1$ events. By the Lovász Local Lemma, if we make sure

 $e(1-m/n)^{d+1}n\leq 1,$

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

 $m\geq n(1-(en)^{-1/(d+1)}).$

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

 $\displaystyle 1-(en)^{-1/(d+1)}\leq(1+\ln(d+1))/(d+1)$ $\displaystyle\iff$ $\displaystyle d+1\geq(d-\ln(d+1))(en)^{1/(d+1)}$ $\displaystyle\iff$ $\displaystyle n\leq\frac{1}{e}(\frac{d+1}{d-\ln(d+1)})^{-1/(d+1)}.$

Let $f(d)=(\frac{d+1}{d-\ln(d+1)})^{-1/(d+1)}$. Note that $\lim_{d\to 0}f(d)=0$; $f^{\prime}(d)\geq 0$ when $d\geq 0$; $\lim_{d\to+\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({{n}\atop{2}}\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({{n}\atop{2}}\right)}$. Hence

 $\displaystyle\Pr[\exists\text{an edge which survives after k times iteration}]$ $\displaystyle\leq{\left({{n}\atop{2}}\right)}\Pr[\text{some fixed edge % survives after k times iteration}]$ $\displaystyle=\frac{n(n-1)}{2}(1-\frac{2m}{n(n-1)})^{k}$ $\displaystyle<\frac{n(n-1)}{2}((1-\frac{2m}{n(n-1)})^{n^{2}/(2m)})^{2\ln n}$ $\displaystyle\leq\frac{n(n-1)}{2}\exp(-2\ln n)$ $\displaystyle=\frac{n(n-1)}{2}\frac{1}{n^{2}}$ $\displaystyle<\frac{1}{2}.$

Thus all the edge is colored after $k$ times iteration with probability at least $1-1/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 $\nexists V_{i}$ s.t. $a\in V_{i}\land 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,\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-1)$ events.

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

 $e(1/k^{2})(4k-1)<1,\forall k\geq 11,$

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\mathcal{H}$, define event $A_{i}$ as all vertices $v\in i$ is assigned same number. Clearly, $\forall i\in\mathcal{H},\Pr[A_{i}]=2\times 2^{-k}=2^{1-k}$. 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},\cdots,A_{|\mathcal{H}|}$ is at most $k^{2}$. Since

 $e2^{1-k}(k^{2}+1)$

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