Probabilistic Methods in Combinatorics
The Probabilistic Method is a powerful tool for tackling many problems in discrete mathematics. It belongs to those areas of mathematics that have experienced the most impressive growth in the past few decades. Roughly speaking, its basic idea can be described as follows. In order to prove existence of a combinatorial structure with certain properties, we construct an appropriate probability space, and show that a randomly chosen element of this space has the desired property with positive probability.
This course provides a gentle introduction to the Probabilistic Method, with an emphasis on methodology. We will try to illustrate the main ideas by showing the application of probabilistic reasoning to various combinatorial problems.
This course provides a gentle introduction to the Probabilistic Method, with an emphasis on methodology. We will try to illustrate the main ideas by showing the application of probabilistic reasoning to various combinatorial problems.
Lecturer
Benjamin Sudakov
Date
21st September ~ 21st December, 2023
Location
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| Thursday | 15:30 - 17:20 | Online | ZOOM 03 | 242 742 6089 | BIMSA |
Prerequisite
It might be helpful to have basic knowledge of combinatorics and probability, but all relevant notions will be defined in the class.
Syllabus
The Basic Method: Ramsey numbers, Set-pairs with restricted intersections
Hypergraph 2-colouring, Tournaments with domination property
Linearity of Expectation: Sum-free subsets, Maximum cut in graphs
The maximum/minimum number of Hamilton cycles and Szele's conjecture
Permanents of Matrices: Minc's Conjecture
The maximum/minimum number of Hamilton cycles and Szele's conjecture
Method of Alterations: Graphs with large girth and large chromatic number
Recolouring and new bounds on non-2-colourable hypergraphs
Dependent random choice and its application to Ramsey and Turán-type problems
Second Moment Method: Turán's proof of the Hardy-Ramanujan theorem
Numbers with distinct sums, Random graphs and threshold functions
Cliques in random graphs
Large Deviations: Chernoff bounds, Consistent arcs in tournaments
Lovász Local Lemma: Proof of the local lemma, 2-colourability, cycles in directed graphs, colouring of integers with all shifts multicoloured
Correlation Inequalities: Four function theorem and a proof of the FKG inequality
Monotone properties in random graphs
Martingales: Chromatic number of random graphs
Isoperimetric inequality for the Hamming cube
Probabilistic Gems: Independence number of triangle-free graphs
Crossing numbers, incidence and additive number theory
Hypergraph 2-colouring, Tournaments with domination property
Linearity of Expectation: Sum-free subsets, Maximum cut in graphs
The maximum/minimum number of Hamilton cycles and Szele's conjecture
Permanents of Matrices: Minc's Conjecture
The maximum/minimum number of Hamilton cycles and Szele's conjecture
Method of Alterations: Graphs with large girth and large chromatic number
Recolouring and new bounds on non-2-colourable hypergraphs
Dependent random choice and its application to Ramsey and Turán-type problems
Second Moment Method: Turán's proof of the Hardy-Ramanujan theorem
Numbers with distinct sums, Random graphs and threshold functions
Cliques in random graphs
Large Deviations: Chernoff bounds, Consistent arcs in tournaments
Lovász Local Lemma: Proof of the local lemma, 2-colourability, cycles in directed graphs, colouring of integers with all shifts multicoloured
Correlation Inequalities: Four function theorem and a proof of the FKG inequality
Monotone properties in random graphs
Martingales: Chromatic number of random graphs
Isoperimetric inequality for the Hamming cube
Probabilistic Gems: Independence number of triangle-free graphs
Crossing numbers, incidence and additive number theory
Audience
Advanced Undergraduate
, Graduate
Video Public
Yes
Notes Public
Yes
Language
English
Lecturer Intro
Benny Sudakov received his PhD from Tel Aviv University in 1999. He had appointments in Princeton University, the Institute for Advanced Studies and in University of California at Los Angeles. Sudakov is currently professor of mathematics in ETH, Zurich. He is the recipient of a Sloan Fellowship, NSF CAREER Award, Humboldt Research Award, is Fellow of the American Math. Society and was invited speaker at the 2010 International Congress of Mathematicians. He authored more than 300 scientific publications and is on the editorial board of 14 research journals. His main scientific interests are combinatorics and its applications to other areas of mathematics and computer science.