Diss. ETH No. 23504 Some Extremal Problems about Saturation and Random Graphs A thesis submitted to attain the degree of Doctor of Sciences of ETH Zurich (Dr. sc. ETH Zurich) presented by Dániel Korándi MASt in Mathematics, University of Cambridge born on February 23, 1990 citizen of Hungary. accepted on the recommendation of Prof. Dr. Benny Sudakov, Examiner Prof. Dr. Jacques Verstraëte, Co-Examiner 2016 Abstract Extremal combinatorics is a major branch of discrete mathematics that studies problems looking for the maximum or minimum size of combinatorial structures satisfying certain properties. Saturation is one of the oldest themes in the area and considers questions of the following form: What is the minimum size of a structure that cannot be extended without creating a forbidden substructure? Another important field is probabilistic combinatorics, that has grown out of extremal combinatorics and studies random combinatorial objects. The Erdős-Rényi random graph G(n, p) is of particular interest, and it is a recent trend in the area to look at classic extremal questions restricted to random graphs. This thesis contributes to the study of saturation problems and of extremal questions in random graphs, including the combination of them: saturation-type problems in random graphs. In Chapter 2 we look at a saturation problem in bipartite graphs and settle a conjecture of Moshkovitz and Shapira in the asymptotic sense. In Chapter 3 we consider the classic saturation problem in random graphs and obtain some tight results. In Chapter 4 we use the differential equation method to analyze a random process that is closely related to weak saturation. As an application, we improve previous results about the fundamental group of random simplicial complexes. In Chapter 5 we look at a classic edge decomposition problem in the random graph setting, and prove some asymptotically correct estimates. ii Zusammenfassung Die extremale Kombinatorik ist ein bedeutender Zweig der diskreten Mathematik. Sie befasst sich mit Fragestellungen über die minimale oder maximale Größe einer kombinatorischen Struktur mit bestimmten geforderten Eigenschaften. Sättigung ist eines der ältesten Themen in diesem Gebiet und studiert Probleme der folgenden Art: Was ist die minimale Größe einer Struktur, die nicht erweitert werden kann ohne eine verbotene Teilstruktur zu erzeugen? Ein weiteres wichtiges Feld ist die probabilistische Kombinatorik, die sich aus der extremalen Kombinatorik heraus entwickelt hat und zufällige kombinatorische Objekte studiert. Hierbei ist der Erdős-Rényi Zufallsgraph G(n, p) von besonderem Interesse. Dies spiegelt sich unter anderem im aktuellen Trend wieder, klassische Fragen der extremalen Kombinatorik auf Zufallsgraphen zu beschränken. Diese Dissertation trägt zur Untersuchung von Sättigungsproblemen und von extremalen Problemen in Zufallsgraphen bei und verbindet diese durch die Untersuchung von Sättigung in Zufallsgraphen. In Kapitel 2 betrachten wir ein Sättigungsproblem in bipartiten Graphen und beweisen eine Vermutung von Moshkovitz und Shapira im asymptotischen Sinn. In Kapitel 3 untersuchen wir das klassische Sättigungsproblem in Zufallsgraphen und erzielen einige scharfe Resultate. In Kapitel 4 benutzen wir die Differentialgleichungsmethode um einen Zufallsprozess zu analysieren, der eng mit der schwachen Sättigung in Graphen zusammenhängt. Diese Analyse verwenden wir, um frühere Resultate über die Fundamentalgruppe von zufällig ausgewählten Simplizialkomplexen zu verbessern. In Kapitel 5 betrachten wir ein klassisches Problem der Kantenzerlegung im Kontext von Zufallsgraphen und beweisen einige asymptotisch korrekte Abschätzungen. iii
© Copyright 2024 ExpyDoc
