Quasi-random hypergraphs and extremal problems for hypergraphs [Elektronische Ressource] / Yury Person

Quasi-Random Hypergraphs and Extremal Problems forHypergraphsDISSERTATIONzur Erlangung des akademischen Gradesdoctor rerum naturalium(Dr. rer. nat.)im Fach Informatikeingereicht an derMathematisch-Naturwissenschaftlichen Fakultät IIHumboldt-Universität zu BerlinvonHerr Dipl.-Math. Univ. Yury PersonPräsident der Humboldt-Universität zu Berlin:Prof. Dr. Dr. h.c. Christoph MarkschiesDekan der Mathematisch-Naturwissenschaftlichen Fakultät II:Prof. Dr. Peter FrenschGutachter:1. PD Dr. Mihyun Kang2. Prof. Dr. Mathias Schacht3. Prof. Dr. Angelika Stegereingereicht am: 23.06.2010Tag der mündlichen Prüfung: 22.11.2010to my motherZusammenfassungDas Regularitätslemma ist ein zentrales Werkzeug aus der Extremalen Graphen-theorie mit Anwendungen in der Additiven Zahlentheorie, der Diskreten Geometrieund der Theoretischen Informatik. Dieses Lemma war ein zentraler Hilfssatz in Sze-merédis Beweis der zahlentheoretischen Vermutung von Erdős und Turán, dass jedeTeilmenge der natürlichen Zahlen mit positiver oberer Dichte arithmetische Progres-sionen beliebiger endlicher Länge enthält.Das Regularitätslemma besagt, dass man die Knotenmenge jedes Graphen in kon-stant viele fast gleich große Teilmengen partitionieren kann, so dass die meisten aufje zwei solcher Teilmengen induzierten bipartiten Graphen quasi-zufällig sind.