[an error occurred while processing this directive][an error occurred while processing this directive][an error occurred while processing this directive][an error occurred while processing this directive] Summer School 2006 - Algorithmen, Struktur, Zufall
Algorithmen, Struktur, Zufall - Hauptseite [an error occurred while processing this directive] Algorithmen, Struktur, Zufall

Summer School 2006

"Extremal Graph Theory and Random Graphs"

Featured speakers: Miklós Simonovits, Yoshiharu Kohayakawa

Chorin, July 31st - August 4th 2006

participants of Summer Schoolparticipants of Summer School

The lectures given on extremal graph theory and random graphs will be supplemented by exercises which will be solved in small groups with solution sessions in the evenings. The language of the school is English.

The summer school is addressed to graduate students and postdocs of Mathematics or Computer Science who are interested in extremal graph theory and random graphs and related fields.

The summer school is supported by DFG within DFG Research Group "Algorithms, Structure, Randomness" and Günter Ziegler's Gottfried Wilhelm Leibniz-Grant.


The summer school will take place in Chorin, 50 km northeast of Berlin.

Hotel Haus Chorin
Neue Klosterallee 10
16230 Chorin

For travel information, see http://www.haus-chorin.de/s1reis_e.htm.

Course material


Extremal graph theory
Miklós Simonovits (abstracts)

Extremal graph theory and Ramsey theory were among the early and fast developing branches of 20th century graph theory. In the introduction we shall begin with describing and providing some sharp theorems (Turán's theorem and Kővári-T. Sós theorem) and then the asymptotic structure of the extremal graphs (the Erdős-Simonovits theory). The introductory part will include description of connections to geometry and hypergraph theory.

This historical introduction will be followed by the classification of ordinary exrtemal graph problems, and the possibility of reducing most non-degenerate extremal graph problems to degenrate extremal graph problems. This and all the subsequent parts will include some important unsolved problems. Thus, e.g., first part will be closed with giving the simplest versions of Turán's famous hypergraph extremal graph problem, and some important related results.

The series of lectures covers the following areas:

  1. Introduction, history and some central theorems
    1. Ramsey theory (Erdős-Szekeres)
    2. Extremal graph theory (Turán/Erdős)
  2. Classification of extremal graph problems and lower bound constructions
    1. The asymptotic structure of extremal graphs
    2. Degenerate extremal graph problems
    3. Lower bound constructions using random graphs and finite geometries
  3. Regularity lemma for graphs
    1. Origins/connections to the existence of arithmetic progressions in dense sequences
    2. Connection to the quantitative Erdős-Stone theorem
    3. First graph theoretic applications (Ruzsa-Szemerédi theorem, Ramsey-Turán problems)
    4. Counting lemma, removal lemma, coloured regularity lemma
  4. Some recent results
    1. 3-coloured Ramsey theorem for cycles
    2. Erdős-Sós conjecture on trees

The theory of random graphs
Yoshiharu Kohayakawa (abstracts)

The theory of random graphs, as conceived by Erdős an Rényi, and first mostly developed by combinatorialists, has now become indispensable to researchers in diverse areas. Thus, random graphs are now popular characters in research papers in combinatorics, computer science, probability, mathematical physics, and biology, among others.

Our main aim in these lectures is to explore several basic features of random graphs that make them of broad interest. We shall often stress the qualitative aspects of interest, at the expense of technical sophistication or sharpness in the result. However, in the aspects of the theory that the lecturer is more familiar with, some of the (interesting) inner guts of the subject will be examined.

Some directions for future research will also be discussed.

In the lectures, we shall give an overview of classical results in the area and we shall touch upon some recent results. More precisely, we shall discuss the following topics:

  1. Introduction
    1. Probabilistic preliminaries
    2. The classical models of random graphs
    3. Jumbledness and expansion
    4. Threshold phenomena
    5. The emergence of the giant component
  2. Properties of random graphs
    1. Subgraph containment: small graphs
    2. Subgraph containment: large graphs
    3. Graph parameters: clique number, chromatic number, diameter, connectivity
  3. Extremal problems
    1. Ramsey and Turán type results for subgraphs of random graphs
    2. Szemerédi's regularity lemma for subgraphs of sparse random graphs and its applications

Not much more than familiarity with elementary probability and basic graph theory will be assumed. In particular, the necessary probabilistc prerequisites will be discussed during the lectures.


Monday, July 31st 2006

13:00 Introduction of Speakers and Participants
13:10 Miklós Simonovits Lecture I: Classical extremal graph theory
16:00 Yoshiharu Kohayakawa Lecture II: Introduction to random graphs
18:00 Joint Dinner

Tuesday, August 1st 2006

9:00 Miklós Simonovits Lecture III: Regularity lemma
12:00 Lunch Break
14:00 Solving Exercises I in groups
18:00 Joint Dinner
19:00 Presentation and Discussion of Solutions to Exercises I

Wednesday, August 2nd 2006

9:00 Yoshiharu Kohayakawa Lecture IV: Properties of random graphs
12:00 Lunch Break

Thursday, August 3rd 2006

9:00 Miklós Simonovits Lecture V: Some recent results
12:00 Lunch Break
14:00 Solving Exercises II in groups
18:00 Joint Dinner
19:00 Presentation and Discussion of Solutions to Exercises II

Friday, August 4th 2006

9:00 Yoshiharu Kohayakawa Lecture VI: Extremal problems for random graphs
12:00 Lunch Break and Closing


Dr. Mihyun Kang, Dr. Mathias Schacht
Postal address
Johann von Neumann-Haus
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin

Tel. : (+49 30) 2093 3830 Fax : (+49 30) 2093 3191 e-mail : school06@informatik.hu-berlin.de