Problems in Positional Games and Extremal Combinatorics

Abstract

This thesis consists of five Chapters. The main purpose of the first chapter is to serve as an introduction. We will define all necessary concepts and discuss the problems that are studied in this thesis as well as stating the main results of it. This thesis deals with two different directions of extremal graph theory. In the first part we consider two kinds of positional games, the so-called strong games and the Maker-Breaker games. In the second chapter we consider the following strong Ramsey game: Two players take turns in claiming a previously unclaimed hyperedge of the complete k-uniform hypergraph on n vertices until all edges have been claimed. The first player to build a copy of a predetermined k-uniform hypegraph is declared the winner of the game. If none of the players win, then the game ends in a draw. The well-known strategy stealing argument shows that the second player cannot expect to ever win this game. Moreover, for sufficiently large n, it follows from Ramsey’s Theorem for hypergraphs that the game cannot end in a draw and is thus a first player win. Now suppose the game is played on the infinite k-uniform complete hypergraph. Strategy stealing and Ramsey’s Theorem still hold and so we might ask the following question: is this game still a first player win or a draw. In this chapter we construct a 5-uniform hypergraph for which the corresponding game is a draw. In the third chapter we consider biased (1 : q) Maker-Breaker games: Two players called Maker and Breaker alternate in occupying previously unoccupied vertices of a given hyper- graph H. Maker occupies 1 vertex per round and Breaker occupies q vertices. Maker wins if he fully occupies a hyperedge of H and Breaker wins otherwise. One of the central questions in this area is to find (or at least approximate) the maximal value of q that allows Maker to win the game. In this chapter we prove two new general winning criteria -one for Maker and one for Breaker- and apply them to two types of games. In the first type, the target is a fixed uniform hypergraph and in the second it is a solution to an arbitrary but fixed linear system of inhomogeneous equations. The second part of this thesis deals with two types of questions from extremal combi- natorics. The first type is of the following form: suppose we are given a certain property of hypergraphs, what is the minimum possible number of edges a k-uniform hypergraph can have such that it does have the property of interest. The second type goes in the different direction. If a certain family of hypergraphs has the minimum number of edges satisfying a certain property, i.e. if the family is extremal in that sense, then how can we characterise it and what operations can we perform while maintaining extremality? In the fourth chapter, we investigate the minimum number f(k) of edges a k-uniform hypergaph having Property O can have. Duffus, Kay and Rödl showed that k! ≤ f(k) ≤ (k2lnk)k!, where the upper bound holds for sufficiently large k. We improve the upper bound by a factor of klnk showing f(k) ≤ ⌊k⌋+1 k!−⌊k⌋(k−1)! for every k ≥ 3. We also answer a question regarding the minimum number n(k) of vertices a k-uniform hypergaph having Property O can have. In the fifth chapter, we consider shattering extremal set systems. A set system F ⊆ 2[n] is said to shatter a given set S⊆[n] if 2^S ={F ∩ S: F ∈ F}. TheSauer-ShelahLemma states that in general, a set system F shatters at least |F| sets. Here we concentrate on the case of equality. A set system is called shattering-extremal if it shatters exactly |F| sets. The so- called elimination conjecture, independently formulated by Mészáros and Rónyai as well as by Kuzmin and Warmuth, states that if a family is shattering- extremal then one can delete a set from it and the resulting family is still shattering-extremal. We prove this conjecture for a class of set systems defined from Sperner systems and for Sperner systems of size at most 4. Furthermore we continue the investigation of the connection between shattering extremal set systems and Gröbner bases.

Diese Dissertation besteht aus 5 Kapiteln. Das erste Kapitel dient als Einleitung und stellt die in der Dissertation behandelten Themen und Ergebnisse vor. Das zweite Kapitel befasst sich mit sogenannten ”strong Ramsey games”, bei denen zwei Spieler ab- wechselnd Kanten des vollst ̈andigen (Hyper-)Graphen beanspruchen. Gewinner des Spiels ist der erste Spieler, welcher einen zuvor fest gewählten (Hyper-)Graphen vollst ̈andig für sich beanspruchen kann. Hat der vollst ̈andige Graph hinreichend viele Knoten, so kann gezeigt werden, dass für den beginnen- den Spieler stets eine Strategie existiert, die es ihm ermöglicht, das Spiel zu gewinnen. Entgegen der allgemeinen Vermutung, dass dies auch auf unendliche vollständige Graphen zutrifft, konstruieren wir einen 5-uniformen Hypergraphen, für den der zweite Spieler ein Unentschieden erzwingen kann. Das dritte Kapitel befasst sich mit sogenannten ‘biased (1 : q) Maker-Breaker’ Spielen. Zwei Spieler, genannt Maker und Breaker, beanspruchen abwechselnd Knoten eines gegebenen Hypergraphen. Maker beansprucht einen Knoten pro Runde und Breaker q Knoten. Maker gewinnt, falls er eine Hyperkante vollständig für sich beanspruchen kann, andernfalls gewinnt Breaker. Eine der zentralen Fragen auf diesem Gebiet ist, die sogenannte threshold bias zu finden. Wir beweisen allgemeine Gewinnkriterien, eins für Maker und eins für Breaker, und wenden diese auf zwei Klassen von Spielen an. Zum Einen verallgemeinern wir ein bekanntes Resultat von Bednarska und Luczak auf Hypergraphen. Zum Anderen bestimmen wir, bis auf eine Konstante, die threshold bias, wenn das Ziel des Spiels eine Lösung zu einem beliebigen, aber festen linearen System von inhomogenen Gleichungen ist. Das vierte Kapitel beschäftigt sich mit der sogenannten Ordnungseigenschaft von geordneten Hyper- graphen, welche kürzlich von Duffus, Kay und Rödl eingeführt worden ist. Wir verbessern die von jenen bewiesene obere Schranke um einen Faktor k ln k. Das letzte Kapitel befasst sich mit dem Begriff des Zerschmetterns (,shatter’). Ein Mengensystem heißt s-extremal, wenn es die Ungleichung von Sauer und Shelah mit Gleichheit erfüllt. Eine Vermutung von Mészáros und Rónyai besagt, dass man zu einem s-extremalen Mengensystem stets eine Menge hinzufügen kann, sodass das resultierende Mengensystem wiederum s-extremal ist. Wir beweisen diese Vermutung für bestimmte Mengensysteme, welche durch sogenannte Sperner Familien definiert werden und für den Fall, dass die Sperner Familie aus höchstens vier Mengen besteht. Zusätzlich beweisen wir ein neues Resultat, welches den Zusammenhang mit Gröbnerbasen weiter beleuchtet.