Progress in nailing the 3-SAT transition bound...

[Subbarao Kambhampati <rao@asu.edu>]

If you are interested in getting an overview of the progress on nailing the 
3-sat phase transition bound, check out

http://www.ipam.ucla.edu/publications/ptac2002/ptac2002_dachlioptas_formulas.pdf

Page 5 in this set of slides gives a nice annotated history of how the 
upper and lowerbounds kept getting tightened.

That page also lists two of the easy proofs, one for a loose upper bound 
(5.191) and another for a loose lower bound (1.637).
The other proofs become progressively more sophisticated...

Rao