Dimitris Achlioptas
Microsoft Research

A New Look at the Second Moment Method

If X is a random variable that is not identically 0, the probability that it takes a value other than 0 is at least E[X]^2 / E[X^2]. This simple inequality underlies "The Second Moment Method", a mainstay of probabilistic combinatorics since the 1950s. Recently, and rather unexpectedly, the second moment method was used to give very sharp bounds for the threshold of Random k-SAT, Random MAX k-SAT, Random Hypergraph Colorability, and Random Graph Coloring.

In all of the above cases, the main contribution was to define an appropriate subset, S, of each problem's solutions such that |S| has small variance. For each problem, this required developing an understanding of the structure of the solution-space. In this talk we will also see that one can, in fact, determine such subsets without such an understanding by instead following a generic, geometric procedure.

If time allows, we will prove the following: with probability that tends to 1 as n tends to infinity, the chromatic number of a random graph G(n,p=d/n) is either k or k+1, where k is the smallest integer such that d < 2k logk.

No prior familiarity with the probabilistic method required.