# Probabilistic Method – 3

February 10, 2011 Leave a comment

Q.1. Given a set and , such that . A coloring of the elements of is a valid 2-coloring if is not monochromatic. Prove that if , there always exists a valid 2-coloring.

Solution.

Randomly, and independently, assign either Red or Blue to each element of with probabilities respectively.

,

By union bound,

If , there exists a valid 2-coloring of .

Put to get the desired result.

Q.2. Ramsey number, Prove that .

Solution.

Consider random graph on vertices where each of the possible edges is sampled with probability .

Take a fixed subset of vertices.

.

We want .

Now, since (and setting ), we will find such that:

, which is true whenever .

Hence, there exist graphs on at most vertices which do not have either a clique or an independent set of size at least .