Regular partitions of hypergraphs and property testing [Elektronische Ressource] / Mathias Schacht. Gutachter: Susanne Albers ; Noga Alon ; Mihyun Kang

Regular partitions of hypergraphs and property testingH a b il i t a ti o n s sc h r i ftzur Erlangung der Lehrbefähigungfür das Fach Informatikvorgelegtdem Rat der Mathematisch-Wissenschaftlichen Fakultät IIder Humboldt-Universität zu BerlinvonMathias Schacht, Ph.D.geboren am 08.04.1977 in BerlinPräsident der Humboldt-Universität zu Berlin:Prof. Dr. Dr. h.c. Christoph MarkschiesDekan der Mathematisch-Wissenschaftlichen Fakultät II:Prof. Dr. Peter FrenschGutachter:1. Prof. Dr. Susanne Albers2. Prof. Dr. Noga Alon3. Priv.-Doz. Dr. Mihyun KangAntrag auf Zulassung zum Habilitationsverfahren: 25.06.2009Zulassung zum Habilitationsverfahren: 06.07.2009Annahme der schriftlichen Habilitationsleistung: 23.11.2009Öffentlicher Vortrag: 15.01.2010ZusammenfassungDie Regularitätsmethode für Graphen wurde vor über 30 Jahren von Szemeré-di, für den Beweis seines Dichteresultates über Teilmengen der natürlichen Zahlen,welche keine arithmetischen Progressionen enthalten, entwickelt. Grob gesprochenbesagt das Regularitätslemma, dass die Knotenmenge eines beliebigen Graphen inkonstant viele Klassen so zerlegt werden kann, dass fast alle induzierten bipartitenGraphen quasi-zufällig sind, d.h. sie verhalten sich wie zufällige bipartite Graphenmit derselben Dichte.