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.


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}.


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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: