printlogo
http://www.ethz.ch/index_EN
Department of Mathematics
 
print
  

Probabilistic Method in Combinatorics

Please note that this page is old.
Check in the VVZ for a current information.


Lecturer: Prof. Benny Sudakov

Thursday 1-3, HG E 33.1

Assistant: Shagnik Das

Monday 4-5, ML J 37.1

Prüfungseinsicht

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

© 2016 Mathematics Department | Imprint | Disclaimer | 12 September 2014
top