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