Spring 2007:  MATH 8823 (Topics in Probabilistic Combinatorics)
 
Jeong Han Kim will deliver the lectures during January and February.
The class meets 1:05-2:55pm on Monday and Wednesday in Skiles 246.

LECTURE NOTES will be posted below as they become available:

  Notes 1 (01/08/07)  
  Notes 2 (01/10/07)  
  Notes 3 (01/22-24/07)  
  Notes 4 (01/31-02/02/07) Lovasz local lemma  
  Notes 5 (02/03-05/07) The nibble and R(3,t)  
  Notes 6 (02/7-14/07) Branching process and G(n,c/n)  
  Presentation Poisson Cloning & Applications  
  Notes 7 (02/19-26/07) Poisson Cloning & Applications (contd.)  
  Notes 8 (02/26-28/07) Contiguity of RG and RRG?  
 


Add to the reading list:
 
(0) D. Achlioptas, Y. Peres: The Threshold for the Random k-SAT is 2^k ln 2 - O(k);  
Jour. of the AMS 17(2004), 947-973.
 
(1) M. Mezard, T. Mora, R. Zecchina: Clustering of Solutions in the Random SAT Problem;  
Phys. Rev. Lett. 94(2005), 197-205. Also, cond-mat/0504070
 
(2) D. Achlioptas, F. Ricci-Tersenghi: On the Solution Space Geometry of Random CSPs;  
Proc. of the ACM STOC (2006), 130-139.   Full version of the paper  
 
(3) M. Mezard, T. Mora, R. Zecchina: Pairs of SAT assignments and Clustering in Random Boolean Formulae.
Available from arxiv or Mora's website:
http://ipnweb.in2p3.fr/~lptms/membres/mora/publi.en.html  
 
(4) B. Cuckler and J. Kahn, Hamilton Cycles in Dirac graphs, to be posted.  
(5) Jon Kleinberg : The Small World Phenomenon: An Algorithmic Perspective  
http://www.cs.cornell.edu/home/kleinber/swn.ps  
(6) Jon Kleinberg : Complex Networks and Decentralized Search Algorithms  
http://www.cs.cornell.edu/home/kleinber/icm06-swn.pdf  
 
PRESENTATIONS:  
 
March 5th, 7th : Jeff Kahn (Rutgers)  
March 12th : Tom Bohman (CMU)  
March 14th : Prasad Tetali : Shearer's result on independence number of $K_r$-free graphs  
April 2nd & 4th : Juan Vera : Preferrential attachment graphs  
April 9th : David Howard/Alex Grigo (Papers 0,1,3)  
April 11th : Prasad Tetali : Johansson's result on chromatic number of triangle free graphs.  
April 16th : Josh Cooper (Univ. of South Carolina)  
April 18th : Brad Green : Jon Kleinberg's work (Papers 5,6)/ Teena Carroll : Entropy & Enumeration  
April 23rd : Mitch Keller/Armen Vagharshakyan  
April 25th : Balinski/Young (Papers (4))