# Probabilistic Method – 3

Q.1. Given a set $S$ and $S_1, \ldots, S_m \subseteq S$, such that $\forall i \mbox{, } |S_i| = l$. A coloring of the elements of $S$ is a valid 2-coloring if $\forall i \mbox{, } S_i$ is not monochromatic. Prove that if $m < 2^{l-1}$, there always exists a valid 2-coloring.

Solution.

Randomly, and independently, assign either Red or Blue to each element of $S$ with probabilities $p \mbox{ and } 1-p$ respectively.

$\forall i$, $Pr[ S_i \mbox { is monochromatic}] = 2[ p^l + (1-p)^l ].$

By union bound, $Pr[ \mbox{ some } S_i \mbox { is monochromatic}] = 2m [ p^l + (1-p)^l ].$

If $2m [ p^l + (1-p)^l ] < 1$, there exists a valid 2-coloring of $S$.

Put $p = 1/2$ to get the desired result.

$-$

Q.2. Ramsey number, $\mathcal{R}(k,l) = min\{ n: \mbox{ any graph on } n \mbox { vertices has a clique of size at least } k$ $\mbox {or an independent set of size at least } l \}.$ Prove that $\mathcal{R}(k,k) > 2^{(k-1)/2}$.

Solution.

Consider random graph $G(n,p)$ on $n$ vertices where each of the $n \choose 2$ possible edges is sampled with probability $p$.

Take a fixed subset $S$ of $k$ vertices.

$Pr[ \mbox{ S is an independent or a clique}] = p^{ k \choose 2 } + (1-p)^{ k \choose 2}$.

$\therefore Pr[ G(n,p) \mbox { has a clique or independent set of size at least } k]$ $\leq { n \choose k} [p^{ { k \choose 2 } } + (1-p)^{ { k \choose 2}}].$

We want ${ n \choose k}[p^{ { k \choose 2 } } + (1-p)^{ { k \choose 2}} ]< 1$.

Now, since ${ n \choose k } \leq n^k$ (and setting $p = 1/2$), we will find $n$ such that:

$n^k \leq 2^{ {k \choose 2} -1}$, which is true whenever $n \leq 2^{(k-1)/2}$.

Hence, there exist graphs on at most $2^{(k-1)/2}$ vertices which do not have either a clique or an independent set of size at least $k$.

$-$