(*) Problem 0.13

Moving forward, I will use a star in the subject to indicate the problem is not easy.

As a first attempt, I tried Erdo's lower bound for Ramsay number. It doesn't work, since larger than the lower bound says nothing about its relative magnitude with the actual Ramsay number.

Now I try the hint on the book.

Pick a node x.

If x's degree is larger than a half of the number of remaining nodes. Then add it to pile A, and dump all the nodes that is not connected to x. Intuitively, we are trying to find a clique, so anything not connected to x is useless. We can dump at most half of the nodes.

Otherwise x's degree is less than a half of the number of remaining nodes. Then add it to pile B, and dump all the nodes that is connected to x. Intuitively, we are trying to find an independent set, so anything connected to x is useless. Again, we can dump at most half of the nodes.

The algorithm proceed until there is no more nodes. Any node in pile A must be connected to each other which means it is a clique. Any node in pile B must not connect to each other which mean it is an independent set.

The algorithm can only throw at most half the number of nodes each time, which means it will take at least $ \log_{2}n $ steps to run. So in the worst case the nodes are distributed evenly so that the size of either clique or independent set is at least $\frac{1}{2}\log_{2}n$.

Q.E.D.

As as aside - this is a genius method - I couldn't have thought about it. I thought about trees (when I see logarithm, but I haven't thought about this simple algorithm)