Discrete Probabilistic Methods (MATH 159, Fall 2009)

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: 380-381T , MF 1:00 - 2:05, W 1:05-2:10.

Instructor: Amir Dembo, Sequoia 129, office hours F 4:15-5:30 or e-mail amir@math.stanford.edu

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

• ``Poisson Approximation'', by Barbour, Holst and Janson (most of Chapter 1, small parts of Chapters 2 and 4).
• ``Large deviations techniniques and applications'', 2nd edition, by Dembo and Zeitouni (parts of Sections 2.1 and 2.4).

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 six teams (of 2-3 students each), where the students in each team will coordinate their presentations of works on the same topic. Attendance in all peer lectures is mandatory for a pass grade. List of topics in order:

• Constructive proof of Lovasz local lemma.
• Games: half-liar, entropy.
• Discrepancy.
• Concentration of measure.
• Random graphs.
• Geometrical applications.

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

• HW1: Ex. 1.1,1.7,1.8,1.9,2.3,2.7
• HW2: Ex. 2.8,3.1,4.1,4.2,4.4,4.5
• HW3: Ex. 5.3,8.2,DZ:2.1.20,2.1.29,2.4.20,2.4.22

Syllabus (out of text or supplements):

         9/21    M(1)            W(2)          F(4)
	 9/28    M(4/3)          W(3/5)        F(5)
	 10/5    M(5)            W(8)          F(8)
	 10/12   M(BJH:1/2)      W(BJH:2/4)    F(App-A;DZ:2.4.1)
	 10/19   W(7.2)          W(7.1-7.4)    F(DZ:2.1.1/2.1.2)
	 10/26   M(--)           W(DZ:2.4.2)   F(6)    
	 11/2    M(6)            W(11)         F(11)
	 11/9    M(Review)       W(St:Supp-5)  F(St:15.6/15.7)
         11/16   M(St:13.2/13.3) W(--)         F(--)
         11/23   M(--)           W(--)         F(--)
	 11/30   M(St:7.5/7.6)   W(St:10)      F(St:14)

See also seminar for current activity in related areas.