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

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.

- Slides from the extremal graph theory lectures
- Slides from the random graphs lectures
- Exercise Set 1
- Exercise Set 2
- Exercise Set 3
- Exercise Set 4

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:

- Introduction, history and some central theorems
- Ramsey theory (Erdős-Szekeres)
- Extremal graph theory (Turán/Erdős)

- Classification of extremal graph problems and lower bound constructions
- The asymptotic structure of extremal graphs
- Degenerate extremal graph problems
- Lower bound constructions using random graphs and finite geometries

- Regularity lemma for graphs
- Origins/connections to the existence of arithmetic progressions in dense sequences
- Connection to the quantitative Erdős-Stone theorem
- First graph theoretic applications (Ruzsa-Szemerédi theorem, Ramsey-Turán problems)
- Counting lemma, removal lemma, coloured regularity lemma

- Some recent results
- 3-coloured Ramsey theorem for cycles
- Erdős-Sós conjecture on trees

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:

- Introduction
- Probabilistic preliminaries
- The classical models of random graphs
- Jumbledness and expansion
- Threshold phenomena
- The emergence of the giant component

- Properties of random graphs
- Subgraph containment: small graphs
- Subgraph containment: large graphs
- Graph parameters: clique number, chromatic number, diameter, connectivity

- Extremal problems
- Ramsey and Turán type results for subgraphs of random graphs
- 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 addressJohann von Neumann-Haus Humboldt-Universität zu Berlin Institut für Informatik Rudower Chaussee 25 12489 Berlin

Tel.: (+49 30) 2093 3830Fax: (+49 30) 2093 3191