Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Block Course: Extremal Combinatorics in Random Discrete Structures

February 27 - March 23, 2012
Freie Universität Berlin

Berlin, Germany


  1. Extremal Combinatorics and the Probabilistic Method -- an Introduction (Tibor Szabo, FU Berlin)
    February 27-March 2, 2012
    Room: Hörsaal 001 (Arnimallee 3)

  2. Multiple Round Exposure in Random Structures
    (Mathias Schacht, University of Hamburg)
    March 5-9 and March 12-16, 2012
    Room: Hörsaal 001 (Arnimallee 3)

  3. Transference Principles (David Conlon, University of Oxford)
    March 15-16 and March 19-23, 2012
    Room: Hörsaal 001 (Arnimallee 3)
       Lectures:   Mon-Fri, 9:00-12:00
       Exercises:  Tue-Fri, 16:00-18:00 


Several classical theorems of combinatorics, such as Turán's theorem, Ramsey's theorem and Szemerédi's theorem, are known to have analogues within sparse random structures. While numerous special cases have been proved over the last twenty years, most notably by Łuczak, Kohayakawa, Rödl and Ruciński, a general treatment giving tight thresholds in all such cases was only obtained very recently. Surprisingly, there are now two very different-looking approaches to doing this, one obtained by Mathias Schacht, the other independently by David Conlon and Tim Gowers. The goal of the course is to see these two approaches next to each other and to compare them, concentrating on their analogies and differences. The plan is to understand the fundamentals and basic ideas of both approaches and fully grasp the proof of at least one special case each, together with a believable notion of how to extend them to their full generality. The course is intended for PhD-students and postdocs interested in the field of Extremal and Probabilistic Combinatorics and related areas. The course will start with a swift introduction to the classical theorems and basic probabilistic techniques. This will lead on to a discussion of techniques that have been used in the past to address problems of this variety, indicating why they cannot be used in the general case. The course will conclude with a thorough discussion of the modern developments given by the authors themselves. Students may choose to join the course at any stage, depending on their individual strengths and interests.


The course is addressed to graduate students and postdocs of Mathematics or Computer Science, who are interested in extremal combinatorics, the theory of random graphs, probabilistic methods and related fields.


A typical day will consist of a morning lecture (9:00-12:00) and an exercise session in the afternoon (16:00-18:00). The exercises are to be solved in small groups in the afternoon and will later be discussed in the exercise session. The language of the course is English.


Applications for participation in the course (the whole or part of it -- please indicate the weeks you plan to participate in), with a short curriculum vitae and scientific background, should be sent by Sept 30, 2011, preferably by email, to Ms Barrett

There is a limited amount of financial support available for PhD-students or for advanced Master/Diploma students in a field related to the topics of the course. Applications for financial support, with curriculum vitae, copies of certificates, thesis, areas of interest, and a letter of recommendation (sent directly by the letter writer) should be sent by Sept 30, 2011, preferably by email, to Ms Barrett at

barrett (at)

Applicants will be notified by Oct 15, 2011.
If there are still places available, the deadline can be extended.


The Block Course is organized as part of the Research Training Group "Methods for Discrete Structures" of the Free University, the Humboldt University and the Technical University in Berlin, and organized by Tibor Szabo.


This is the place where you find hints on how to find reasonably priced accomodation, how to get around Berlin, and the like. If there is anything missing, let us know. (Most of the links lead to German pages, sorry.)