Extremal hypergraph theory and algorithmic regularity lemma for sparse graphs [Elektronische Ressource] / Hiêp Hạ̀n. Gutachter: Mihyun Kang ; Anuschirawan Taraz ; Hanno Lefmann

Extremal Hypergraph Theory and Algorithmic RegularityLemma for Sparse GraphsDISSERTATIONzur Erlangung des akademischen GradesDOCTOR RERUM NATURALIUMim Fach Informatikeingereicht an derMathematisch-Naturwissenschaftlichen Fakultät IIHumboldt-Universität zu BerlinvonDipl.-Inf. Hiêp Hàn.Präsident der Humboldt-Universität zu Berlin:Prof. Dr. Dr. h.c. MarkschiesDekan der Mathematisch-Naturwissenschaftlichen Fakultät II:Prof. Dr. FrenschGutachter:1. PD Dr. Mihyun Kang2. Prof. Dr. Anuschirawan Taraz3. Prof. Dr. Hanno Lefmanneingereicht am: 16.01.2010Tag der mündlichen Prüfung: 07.10.2010AbstractOnce invented as an auxiliary lemma for Szemerédi’s Theorem [106] the regularitylemma [105] has become one of the most powerful tools in graph theory in the lastthree decades which has been widely applied in several fields of mathematics andtheoretical computer science.Roughly speaking the lemma asserts that dense graphs can be approximated by aconstant number of bipartite quasi-random graphs, thus, it narrows the gap betweendeterministic and random graphs. Since the latter are much easier to handle thisadditional information is often very useful.With Szemerédi’s regularity lemma as the starting point two roads diverge inthis thesis aiming at applications of the concept of regularity on the one hand andclarification of several aspects of this concept on the other.