Course Details
Listed below are the administrative details regarding the course.
Registration
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.
Schedule
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!
Instructors
Shagnik Das
shagnNOBOTSHEREik@mi.fu-berHAHAHAHAHAHAHAlin.de
Tibor Szabó
szaNOBOTSHEREbo@math.fu-berHAHAHAHAHAHAHAlin.de
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.
Credits
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.
Topics
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.
References
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.
Prerequisites
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
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 www.flaticon.com for the icons.
Schedule
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 |
Exercises
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
lamaNOBOTSHEREison@math.fu-berHAHAHAHAHAHAHAlin.de
Patrick Morris
pm0NOBOTSHERE041@math.fu-berHAHAHAHAHAHAHAlin.de
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 |