** Instructor Info **

- Name: Bojan Mohar
- Email: mohar (at) sfu (dot) ca
- Office Hours:
**Wed 2:00-3:00**or through appointment by e-mail - Lectures:
**Mon 14:30-16:20**and**Wed 10:30-12:20**@ K9509

**Textbook**

N. Alon, J. Spencer, *The Probabilistic Method*, Wiley, 1992.

Additional course notes may be distributed.

**Grade Division**

- 40% Final Exam
- 40% HW Exercises
- 20% Presentation of Report (Graded primarily on an effort/improvement basis)

This scheme may be adjusted slightly as circumstances warrant.

**Course Description**

The main theme of the course will be concerned with applications of probabilistic methods in discrete mathematics. The basics theory was developed by Erdos and Renyi in the 1950's. Today, this is one of the inevitable tools in modern combinatorics, and has enabled profound applications in graph theory, combinatorics, discrete geometry, number theory, and theoretical computer science. On the other hand, all these applications motivated further development of probability theory, where important new areas have been discovered.

We shall uncover the beauty of this subject by following the textbook written by Noga Alon and Joel Spencer.

The following topics will be covered:

- Basic probabilistic method
- Second moments
- Lovasz local lemma
- Correlation inequalities
- Martingales and Azuma inequality
- Random graphs
- Discrepancy theory
- Derandomization (if time permits)

Each of the above lecture topics will take about 1-2 weeks.

Students will be asked to present some of the topics in an informal Instructional-Seminar-like setting.

**Prerequisites**

- Basic course in probability theory (only discrete distributions will be needed)
- Basic course in graph theory (or discrete mathematics)

**Homework** (due a week after being appointed): NOT AVAILABLE BEFORE THE
DATE SHOWN

- Homework Assignment #1 (September 19)
- Homework Assignment #2 (October 3)
- Homework Assignment #3 (October 17)
- Homework Assignment #4 (October 31)
- Homework Assignment #5 (November 14)
- Take home exam (November 28)