The Probabilistic Method

Summer 2020

FU Berlin, Mathematics and Informatics

Course Details

Listed below are the administrative details regarding the course.


If you are interested in taking this course, please make sure you register in the Whiteboard system. (Instructions for registration, and for non-FU students.) It is important to do this as soon as possible, so that we can contact you if needed.

We also ask that you please complete this form, so that we know a bit about your combinatorial background.


In keeping with the university's coronavirus guidelines and maintaining a responsible level of social distancing, all course activities will take place online through the Cisco Webex Meetings platform. Please be sure to have installed and familiarised yourself with any necessary software in advance. Information for setting up an account for FU students can be found in the ZEDAT portal. Once installed, you can test your configuration here.

Starting from the 21st of April, lectures will take place on Tuesdays and Thursdays, from 10:30 to 12:00. The links to the Webex meetings will be available in the Whiteboard system. Roughly every second week, the second lecture will be replaced with an exercise session to discuss solutions to the problem sheets. See below for more details about the schedule.

We have heard that these times do not suit everyone, and would like to see if there is a mutually more convenient time. Please fill out this survey to let us know when you would be free to attend the course. Thank you!


Shagnik Das

Tibor Szabó

Office hours (virtual, of course) are available by appointment, so please e-mail us as needed.

Exams and Requirements

The final grade for this course will come from an oral exam. These will be scheduled later in the semester.

The full set of requirements and formalities for the course can be found here.


Master's students at the Freie Universität Berlin may take this course either as "Diskrete Mathematik III" module or as an "Ergänzungsmodul: Ausgewählte Themen" A, B, or C.

Phase I students from the Berlin Mathematical School may take this course as an advanced course in teaching area 4.

Return to top


In this course we will survey the probabilistic method and several applications in combinatorics, geometry and theoretical computer science.

Specific topics include linearity of expectation, the method of alterations, the second moment method, the Lovász Local Lemma, correlation and concentration inequalities, pseudorandomness and random graphs. We hope to finish by presenting the recent breakthrough of Frankston, Kahn, Narayanan and Park on fractional expectation thresholds.


We shall be using the following text, which is strongly recommended not only for this course but for life in general:

  • N. Alon and J. H. Spencer, The Probabilistic Method
  • Some additional references that could be useful are:

  • B. Bollobás, Random Graphs
  • S. Janson, T. Łuczak and A. Ruciński, Random Graphs
  • M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method
  • Slides from the lectures will be available from this website, but they will not be complete. You are encouraged to take your own notes.


    This course is the third element in the Discrete Maths sequence. Successful completion of Discrete Maths I (or equivalent; contact the instructors for consent) is required, and completion of a Discrete Maths II course would be beneficial.

    Basic knowledge of combinatorics and graph theory, probability, linear algebra and calculus is required.

    Return to top


    Slides will be made available below a few days before their corresponding lectures. If applicable, annotated versions will be provided after the lecture.

    Chapter Slides Last modified
    0. Why? What? How? May 5
    1. Getting Started May 21
    2. Method of Alterations May 7
    3. The Second Moment May 20
    4. The Lovász Local Lemma Jun 1
    5. Concentration Jun 18
    6. The Rödl Nibble Jun 29
    7. Expectation Thresholds Jul 14

    Many thanks to Freepik from for the icons.

    Return to top


    Below is the detailed schedule for the course events.

    A brief summary of the topics and relevant references for each lecture is given below.

    Date Topics Slides Alon-Spencer
    April 21 Course introduction
    Unsatisfiable k-SAT formulae
    Ch 0
    Ch 1, Sec 1
    April 23 Prefix-free codes
    Sum-free subsets
    Ch 1, Sec 2
    Ch 1, Sec 3

    Sec 1.4
    April 28 Dominating tournaments
    Ramsey numbers
    Ch 1, Sec 4
    Ch 1, Sec 5
    Sec 1.2
    May 5 Ramsey via alterations
    Dominating graphs
    Dependent random choice: intro
    Ch 2, Sec 1
    Ch 2, Sec 2
    Ch 2, Sec 3
    Sec 3.1
    Sec 1.2
    May 7 Dependent random choice
    Markov and Chebyshev Inequalities
    Ch 2, Sec 3
    Ch 3, Sec 1
    Prob Lens, Ch 17
    Sec 4.1
    May 12 Existence of thresholds
    Subgraphs in G(n,p)
    Ch 3, Sec 2
    Ch 3, Sec 3

    Sec 4.4
    May 19 Prime factors
    Distinct sum sets
    Ch 3, Sec 4
    Ch 3, Sec 5

    Sec 4.2
    Sec 4.6
    May 21 Lovász Local Lemma:
    symmetric and general
    Ch 4, Sec 1
    Ch 4, Sec 2

    Sec 5.1, 5.3
    May 26 Proof of the LLL
    Transversals and the LLLL
    Ch 4, Sec 3
    Ch 4, Sec 4
    Sec 5.1
    Sec 5.6
    Jun 2 Latin transversals
    Chernoff bounds
    Ch 4, Sec 4
    Ch 5, Sec 1
    Sec 5.6
    Sec A.1
    Jun 4 Asymptotics of R(3,k) Ch 5, Sec 2 Prob Lens, Appendix A
    Jun 9 Asymptotics of R(3,k)
    Hamiltonicity of G(n,p)
    Ch 5, Sec 2
    Ch 5, Sec 3
    Prob Lens, Appendix A
    Jun 16 Azuma's Inequality
    Probability of triangle-freeness
    Ch 5, Sec 4
    Ch 5, Sec 5
    Sec 7.1-2
    Jun 18 Concentration of chromatic numbers Ch 5, Sec 6 Sec 7.3
    Jun 23 The Erdős-Hanani Conjecture Ch 6, Sec 1 Sec 4.7
    Jun 30 Proof of Pippinger's Theorem Ch 6, Sec 2-3 Sec 4.7
    Jul 2 Completion of Pippinger's Theorem
    Introduction to expectation thresholds
    Ch 6, Sec 3
    Ch 7, Sec 1
    Sec 4.7
    Jul 7 Fractional expectation thresholds
    Application: subgraph containment
    Ch 7, Sec 1
    Ch 7, Sec 2
    Return to top


    Homework assignments will be posted below, and to the Whiteboard site, every two weeks, and you will have a week to solve them. You should submit your typed or scanned solutions on the Whiteboard site.

    You will then discuss these exercises in small groups during the exercise sessions, where you are expected to present your answers, listen to your colleagues' solutions, and explore alternative methods and/or related problems. When presenting a solution, you will be able to share a file in the Webex meeting, so that your classmates will be able to follow along. You can use the same file that you submit to us, but you are also welcome to prepare a separate file for the specific problem, should you want to present it in a certain way.

    Check the course formalities for more details.

    Session leaders

    Ander Lamaison

    Patrick Morris

    Exercise sheets

    Assignment Due date Comments
    Sheet 1 April 30 [28/4] Exercise 4 - coefficients are positive integers
    Sheet 2 May 14 [12/5] Exercise 4 - range of p restricted, hint added
    Sheet 3 May 28 [27/5] Exercise 5 - only for large k
    Sheet 4 Jun 11
    Sheet 5 Jun 25
    Sheet 6 Jul 9 [6/7] Exercise 5 - reference to 4(b) corrected; Exercise 6 - added
    Sheet 7 Jul 16 [14/7] Exercise 5 - constant corrected
    Return to top