The talk was based on [9] and consisted in a presentation of various tail bounds for occupancy problems and applications to the determination of the conjectured satisfiability threshold in the random ksat problem.
E 
é ê ê ë 
X_{n} 
æ ç ç è 
t+ 

ö ÷ ÷ ø 
F_{t} 
ù ú ú û 
= 
æ ç ç è 
1 

ö ÷ ÷ ø 
X_{n}(t). 
P{X_{n}(t)Î A}£(2p n)^{1/2} exp  (  nh  (  e^{t}+e,e^{t}  )  ) 
E  [  M_{n}(s+h)F_{s}  ]  =E  [  E  [  X_{n}(t)F_{s+h}  ]  F_{s}  ]  =E  [  X_{n}(t)F_{s}  ]  =M_{n}(s). 
P  {  \vert  X_{n}(t)E  [  X_{n}(t)  ]  \vert  >ne  }  £2exp 
æ ç ç è 
 

ö ÷ ÷ ø 
. (3) 
 

. 


logP  {  X_{n}(t)³ nx  }  =inf  _{x(0)=1, x(t)=x}  ó õ 

h 
æ ç ç è 
 

(s),x(s) 
ö ÷ ÷ ø 
ds. (4) 
E_{F}  [  T(F)  ]  =E_{F} 
é ê ê ë 


ù ú ú û 
= 

E_{F} 
é ê ê ë 

ù ú ú û 
=2^{n} E_{F} 
é ê ê ë 

ù ú ú û 
, (5) 
æ ç ç è 

ö ÷ ÷ ø 
^{cn}E_{F}' 
é ê ê ë 

ù ú ú û 
, 
n 
3 
P{F is satisfiable } £ 
æ ç ç è 

ö ÷ ÷ ø 
^{cn}E_{F}'  [  2^{#I}  ]  . (6) 
http://www.math.wisc.edu/~kurtz/feng/ldp.htm
.This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.