|
Lecturer: Prof. Benny Sudakov
Thursday 1-3, HG E 33.1
Assistant: Shagnik Das
Monday 4-5, ML J 37.1
Für die Prüfung vom Sommer 2014 bieten wir im HG G19.1 die folgenden Einsichten an: 17. (15:00 bis 17:00), 18., 23., 26. und 30. September sowie 3. Oktober jeweils von 12:00 bis 14:00.
Falls die Termine verpasst wurden, können Sie Ihre Prüfung
auch in der Semesterpräsenz anschauen. Sie findet ab der vierten
Semesterwoche jeweils Dienstags und Mittwochs von 12-13 Uhr im HG J 15.1 statt und wird von einem Assistenten betreut. Weitere Infos unter http://www.math.ethz.ch/~gruppe1/ .
Die Einsichtnahme kann nur gegen Vorweisen der Legi erfolgen.
Course Description:
The Probabilistic Method is a powerful tool for tackling many problems in discrete mathematics. It belongs to those areas of mathematics that have experienced a 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. The topics covered in the class will include (but are not limited to):
Linearity of expectation, the second moment method, the local lemma, correlation inequalities, martingales, large deviation inequalities, Janson and Talagrand inequalities and pseudo-randomness.
Sample Reading List:
Most of the topics covered in the course appear in the book listed below (especially the first one). Other topics appear in recent papers.
Assignments:
Through the course of the term, homework assignments will be posted here.
Course Syllabus:
We will cover the following topics this semester. This outline may be updated as the term progresses.
Subject | Topics |
The Basic Method |
Ramsey numbers Set-pairs with restricted intersections Hypergraph 2-colouring Sum-free subsets |
Linearity of Expectation |
Dominating sets and applications to covering codes Maximum cut in graphs |
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 |
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
Applications: 2-colourability, cycles in directed graphs, acyclic edge colouring, 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 |
Ramsey and Turán numbers of sparse graphs Independence number of triangle-free graphs Crossing numbers, incidence and additive number theory |
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne
graphische Elemente dargestellt. Die Funktionalität der
Website ist aber trotzdem gewährleistet. Wenn Sie diese
Website regelmässig benutzen, empfehlen wir Ihnen, auf
Ihrem Computer einen aktuellen Browser zu installieren. Weitere
Informationen finden Sie auf
folgender
Seite.
Important Note:
The content in this site is accessible to any browser or
Internet device, however, some graphics will display correctly
only in the newer versions of Netscape. To get the most out of
our site we suggest you upgrade to a newer browser.
More
information