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)

See also seminar for current activity in related areas.