### 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):

• ``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 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:

• Any chapter of text-book, not already covered in lectures.
• Supplements: Concentration of measure (examples from the literature).
• Supplements: Poisson approximation (examples from BJH text).
• Supplements: On random graphs (from the literature).
• Constructive proof of Lovasz local lemma.

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):

```     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)
```