[Computational Complexity] Dispersing Ramsey Graphs
Perhaps the very first example one sees of the probabilistic method: Show there exists a graph on n vertices with no clique or independent set of size k = 2log n. Simply pick the graph at random. For any set S of k vertices the probability that the graph restricted to S will be a clique or independent set is at most p=2-(k choose 2)/2. The probability that any subset S is a clique or independent is at most p times (n choose k) which is less than one for k = 2log n. So there must be some graph with no clique or independent set of size k.
Actually constructing such a Ramsey graph is another story. You can create the graph in quasipolynomial (2poly log n) time using standard derandomization techniques. In 1981, Frankl and Wilson had a polynomial-time construction of a graph that had no clique or independent sets of size 2(log n log log n)1/2. That bound stood until the recent STOC paper by Barak, Rao, Shaltiel and Wigderson creating a graph with no clique or independent set of size 2(log n)o(1).
Barak et. al. were not trying to create Ramsey graphs, rather to create randomness dispersers for two independent weakly random sources. As a bonus they improved the Frankl-Wilson bound giving yet another example where proving one kind of theorem in complexity gives an exciting result in an apparently unrelated area.
Posted by Lance to Computational Complexity at 5/31/2006 07:59:00 AM