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!
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.
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:
Some additional references that could be useful are:
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.
Slides will be made available below a few days before their corresponding lectures. If applicable, annotated versions will be provided after the lecture.
Many thanks to Freepik from www.flaticon.com for the icons.
Below is the detailed schedule for the course events.
A brief summary of the topics and relevant references for each lecture is given below.
|April 21||Course introduction
Unsatisfiable k-SAT formulae
Ch 1, Sec 1
|April 23||Prefix-free codes
|Ch 1, Sec 2
Ch 1, Sec 3
|April 28||Dominating tournaments
|Ch 1, Sec 4
Ch 1, Sec 5
|May 5||Ramsey via alterations
Dependent random choice: intro
|Ch 2, Sec 1
Ch 2, Sec 2
Ch 2, Sec 3
|May 7||Dependent random choice
Markov and Chebyshev Inequalities
|Ch 2, Sec 3
Ch 3, Sec 1
|Prob Lens, Ch 17
|May 12||Existence of thresholds
Subgraphs in G(n,p)
|Ch 3, Sec 2
Ch 3, Sec 3
|May 19||Prime factors
Distinct sum sets
|Ch 3, Sec 4
Ch 3, Sec 5
|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
|Jun 2||Latin transversals
|Ch 4, Sec 4
Ch 5, Sec 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
|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
|Jul 7||Fractional expectation thresholds
Application: subgraph containment
|Ch 7, Sec 1
Ch 7, Sec 2
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.
|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|