Problems on Random Graphs and Set Systems
Vieira, Pedro · Repository for Publications and Research Data (ETH Zurich) · 2017
This thesis is divided into two parts.The first part contributes to the study of algorithmic-type problems in random graphs, whereas the second part addresses several extremal questions about set systems with restricted intersections.Random Graphs is a major branch of modern Combinatorics concerned with the study of graphs arising from certain probability distributions or random processes.Many questions about random graphs concern the Erdős-Rényi random graph model G(n, p) and are of the following form: given a property of graphs P, how large does p need to be in order for G(n, p) to typically satisfy P? If p is large enough, it is natural to inquire whether one necessarily needs to reveal the whole random graph in order to verify that it satisfies P. In Chapter 2 we consider an algorithmic version of this question, by asking for the minimum number of edges of G(n, p) that necessarily need to be revealed by any adaptive algorithm in order to almost surely expose a subgraph of G(n, p) which already satisfies P. We answer this question for the cases where P is connectedness, Hamiltonicity and the existence of certain paths.Another important branch of Combinatorics is Extremal Set Theory, which typically studies problems looking for the maximum or minimum size of set systems (i.e.families of sets) satisfying certain properties.In Chapter 3 we consider several variants of some classical results in Extremal Set Theory, namely Fisher's inequality and the Oddtown/Eventown problem.First we address a defect version of Fisher's inequality, introduced by Vu, and provide new exact and asymptotic bounds.Secondly, we provide a stability result to a theorem of Vu about eventowns for multiple intersections.Finally, we improve some previously known bounds to several defect versions of the Oddtown problem.ii Zusammenfassung Diese Doktorarbeit besteht aus zwei Teilen.Der erste Teile untersucht algorithmische Probleme im Zusammenhang mit Zufallsgraphen, wohingegen der zweite Teil mehrere Fragen zu extremalen Mengensystemen mit eingeschrnkten Durchschnitten behandelt.Das Gebiet der Zufallsgraphen ist ein Hauptzweig der modernen Kombinatorik.Es betrachtet Graphen, die durch gewisse Zufallsverteilungen oder Zufallsprozesse erzeugt werden.Viele Fragestellungen betreffen das Erdős-Rényi-Modell G(n, p) von Zufallsgraphen und sind von folgender Art: Sei P eine Eigenschaft von Graphen.Wie gross muss dann p sein, damit G(n, p) typischerweise P erfllt?Bei hinreichend grossem p liegt die Frage nahe, ob notwendigerweise der ganze Graph enthllt werden muss, um zu berprfen, ob P erfllt ist.Im zweiten Kapitel betrachten wir algorithmische Versionen dieser Probleme; wir fragen nach der minimalen Anzahl Kanten von G(n, p), welche notwendigerweise enthllt werden mssen, um fast sicher einen P erfllenden Teilgraph von G(n, p) freizulegen.Wir geben eine Antwort fr die Flle, in denen die Eigenschaft P zusammenhngend, hamiltonisch und die Existenz von gewissen Wegen bedeutet.Ein anderer wichtiger Zweig der Kombinatorik ist die extremale Mengentheorie.Diese behandelt typischerweise Probleme zur Bestimmung maximaler oder minimaler Grssen von Mengensystemen (i.e.Familien von Mengen), welche gewisse Eigenschaften erfllen.In Kapitel 3 betrachten wir mehrere Varianten klassischer Resultate der extremalen Mengentheorie, namentlich Fischers Ungleichung und das Oddtown/Eventown Problem.Zuerst besprechen wir eine von Vu eingefhrte Defektversion von Fisher's Ungleichung und geben neue exakte und asymptotische Schranken.Dann zeigen wir ein Stabilittsresultat zu einem Satz von Vu ber Eventown fr mehrere Durchschnitte.Schliesslich verbessern wir bereits bekannte Schranken zu mehreren Defektversionen des Oddtown-Problems.iii First and foremost I want to thank my advisor, Benny Sudakov, for all the guidance and support he has provided me over the course of my PhD.Working with Benny has been a truly wonderful and rewarding experience.I am very grateful for his relaxed, hard-working and fair attitude, for his immense availability and openness to discuss ideas, and for the great care he has had for me.I am just as indebted to my family, who have stood by my side throughout my life.Without their support and encouragement none of this would have been possible.Special thanks to my grandfather Manuel, for sharing with me his passion for the beauty of mathematics since I was a little boy.Growing up