Discrete Probabilistic Methods (MATH 159, Winter 2014)

We shall review discrete probabilistic methods suitable for analyzing discrete structures of the type arising in number theory, graph theory, combinatorics, computer science, information theory and molecular sequence analysis.

Meeting: McCullough 126, MWF 12:50 - 2:05.

Instructor: Amir Dembo, Office hours M 11:15-12:15, F 2:15-3:05, Sequoia 129, or e-mail.

Text: ``The probabilistic method'' by Alon and Spencer, 3rd edition. Supplements from following texts (on reserve at math. library):

Prerequisite: STATS 116/MATH 151 or equivalent.

Grading: Each registered student is to give a 20min presention on a topic from part II of the text book, or any other topic of interest to the class. We shall have nine teams (3 students each), where the students in each team will coordinate their presentations of works on the same topic (to be delivered on the same date). Attendance in all but two peer lectures is mandatory for a pass grade.

List of potential topics:

Recommended to solve six of the following problems from the text (non-mandatory homework):

Syllabus (out of text or supplements):

     1/6     M(1/2)            W(2/4)          F(1/4/3)
     1/13    M(3)              W(5)            F(5)
     1/20    M(--)             W(8)            F(8)          
     1/27    M(BJH:1/2)        W(BJH:2/4)      F(App-A:DZ:2.4.1)    
     2/3     M(7.2)            W(7.1-7.5)      F(DZ:2.1.1/2.1.2)    
     2/10    M(7.6)            W(6)            F(6)    
     2/17    M(--)             W(11.4-11.5)    F(11.6-11.8)         
     2/24    M(St;15.7)        W(St;11.9/10)   F(St;BJH:5.1/2)  
     3/3     M(St;10.1-10.3)   W(St;Loc-Lemma) F(St;7.7+supp)  
     3/10    M(St;17.3)        W(St;13.1/2)    F(St;DZ:3.7.4)

See also seminar for current activity in related areas.