On problems in Extremal Combinatorics

Abstract

Extremal Combinatorics studies how large or how small a structure can be, if it does not contain certain forbidden configuration. One of its major areas of study is extremal set theory, where the structures considered are families of sets, and the forbidden configurations are restricted intersection patterns. A fundamental result in this direction is the Erd\H{o}s-Ko-Rado theorem from 1961 which determines the maximum size of uniform intersecting families. Another central area is extremal graph theory, in which the structures being studied are graphs, and the configurations to be avoided are given subgraphs. A basic result in this area is the Tur\'an's theorem, which gives the maximum number of edges in graphs with no copy of a given clique. Inspiring from these theorems, countless extensions and variations have been developed. We shall discuss some of them in subsequent chapters. One of the very active areas of research related to popular recreational games (e.g. Tic-Tac-Toe and Hex) is positional games. It enjoys fruitful interconnections with other combinatorial disciplines such as Ramsey theory, probabilistic combinatorics, and theoretical computer science. In the most general form, a positional game is a perfect information game described by a finite set of positions (the board) and by a family of subsets of the board (winning sets). Two players then alternatively claim previously unclaimed positions until they fully occupy the board. Different types of positional games are characterised by (different) rules that are used to determine the winner. In this dissertation, we focus on various aspects of extremal combinatorics, including positional games, as well as the employment of the spectral method and the stability approach to study extremal problems. In Chapter 2, we use linear algebra methods to study the stability of the Erd\H{o}s-Ko-Rado theorem. In particular, we show that every set system with few disjoint pairs can be made intersecting by removing few sets. Armed with this result, we settle a conjecture of Bollob\'as, Narayanan and Raigorodskii (2014) regarding the independence number of random subgraphs of the Kneser graph. In Chapter 3, we investigate an Erd\H{o}s-Rothschild-type strengthen of the Erd\H{o}s-Ko-Rado theorem. We then shift to extremal graph theory, and in Chapter 4 study a multipartite version of the Turan's Theorem via a stability approach. Amongst other things, we greatly extend the work of Pfender on the topic. The last part of the dissertation deals with Avoider- Enforcer games. We obtain essentially optimal upper bounds on the threshold biases for the Avoider-Enforcer non-planarity game thus addressing a question and substantially improving the results of Hefetz, Krivelevich, Stojakovic and Szab\'o (2008).

Das Gebiet der Extremalen Kombinatorik beschäftigt sich mit der folgenden grundlegenden Frage: ,,Wie groß kann eine Struktur sein, wenn sie keine verbotenen Teilstrukturen enthält?" Die studierten Strukturen sind dabei äußerst flexibel, sodass sie eine große Bandbreite an Anwendungen in verschiedensten Fachgebieten, wie der Theoretischen Informatik, dem Operations Research, der Diskreten Geometrie und der Zahlentheorie, ermöglichen. Vieles in der Extremalen Kombinatorik betrifft Klassen von Mengen, was Extremale Mengentheorie genannt wird. Zum Beispiel: Was ist die größte Anzahl k-elementiger Teilmengen einer n-elementigen Menge, die sich paarweise schneiden können? Die Antwort auf diese Frage, nämlich der Satz von Erd\H{o}s -Ko-Rado, hatte viele Fragestellungen in der Extremalen Mengenlehre zu Folge. In dieser Dissertation stellen wir neue Erweiterungen klassischer Theoreme der Extremalen Kombinatorik vor, wobei wir probabilistische und analytische Argumente verwenden. In Kapitel 2 nutzen wir die analytische Methode, um die Stabilität des Erd\H{o}s-Ko-Rado-Theorems zu untersuchen. Insbesondere zeigen wir, dass jedes Mengensystem, welches wenige disjunkte Paare enthält, durch Wegnahme weniger Mengen überschneidend gemacht werden kann. Mit diesem Resultat ausgerüstet, klären wir eine Frage von Bollob\'as, Narayanan and Raigorodski (2014) bezüglich der Unabhängigkeitszahl von Zufallsgraphen des Knesergraphs. In Kapitel 3 untersuchen wir eine Variante des ursprünglichen Problems von Erd\H{o}s und Rothschild, in dem wir disjunkte Paare von Hyperkanten gleicher Farbe verbieten. Unsere Resultate erweitern das Erd\H{o}s -Ko-Rado-Theorem. Danach schreiten wir zur Extremalen Graphentheorie und studieren in Kapitel 4 eine multipartite Version des Satzes von Tur\'an, wobei wir die probabilistische Methode in Verbindung mit einem Stabilitätsansatz verwenden. Der letzte Teil dieser Arbeit behandelt Avoider-Enforcer-Spiele, in denen zwei Spieler abwechselnd Kanten des vollständigen Graphs einnehmen. Avoider gewinnt, wenn es ihr gelingt zu vermeiden, dass sie alle Kanten einer Verlierermenge besetzt. In diesem Kapitel erhalten wir im Wesentlichen optimale obere Schranken für die ,,threshold biases" des ,,non- planarity"-Spiels und des ,,non-k-colourability"-Spiels, womit wir eine Frage von Hefetz, Krivelevich, Stojakovi\'c und Szab\'o (2008) aufgreifen und deren Resultate bedeutend verbessern.