Orientation Games and Minimal Ramsey Graphs

Abstract

In this thesis, we consider problems of two different directions in extremal graph theory. In the first part, we study orientation games, which are a variation of positional games. Two players, referred to as OMaker and OBreaker, alternately direct edges of K_n, the complete graph on n vertices. OMaker wins the game if the final complete digraph (a tournament) has some predefined property P. Otherwise, OBreaker wins. Orientation games were studied by several researchers, including Aigner, Alon, Beck, Ben-Eliezer, Bollobás, Krivelevich, Sudakov, Szabó, Tuza and many others. For a given tournament T_k on k vertices, we consider the orientation-tournament game Or(T_k) in which the property P OMaker tries to achieve is that the final tournament contains a copy of T_k. We show that OMaker can win this game whenever k < (2-o(1)) log_2 n, whereas OBreaker has a winning strategy when k is roughly of order 4 log_2 n. For the lower bound, we work in a setting studied earlier by Beck and Gebauer where OMaker wins if and only if the digraph consisting merely of her directed edges contains the given tournament T_k. We improve the best known constant factor. Moreover, our lower bound is tight for this setting, as is implied by the criterion of Erdos and Selfridge. The second orientation game we consider is the oriented-cycle game, where OMaker wins if the final tournament contains a directed cycle. As was recently shown by Ben-Eliezer, Krivelevich and Sudakov, OMaker has a winning strategy in this game even when OBreaker is allowed to direct up to roughly n/2 edges in each round. Let b be the number of edges OBreaker is allowed to direct in one round. As was observed by Bollobás and Szabó, OBreaker can win if b> n-3. We improve this trivial upper bound and show that OBreaker has a winning strategy when b> 5n/6+1. We adjust our strategy to the case when OBreaker is required to direct exactly b edges and thus refute a conjecture by Bollobás and Szabó. In the second part, we study minimal Ramsey graphs. A graph G is r-Ramsey for a graph H if every r-colouring of the edges of G contains a monochromatic copy of H. A graph G is r-Ramsey minimal for a graph H if it is r-Ramsey for H, but no proper subgraph of G is r-Ramsey for H. Let s_r(H) be the smallest minimum degree an r-Ramsey graph of H can have. The study of s_2(H) was introduced by Burr, Erdos, and Lovász, who showed that s_2(K_k)=(k-1)^2. In this thesis, we settle a question by Szabó, Zumstein, and Zürcher and prove that s_2(K_k . K_2)=k-1, where K_k . K_2 is the graph on k+1 vertices consisting of K_k with a pendant edge. This has the following interesting consequence. Two graphs H and H' are Ramsey-equivalent if every graph G is 2-Ramsey for H if and only if it is 2-Ramsey for H'. A famous theorem of Nesetril and Rödl implies that any graph H which is Ramsey- equivalent to K_k must contain K_k. Our result implies therefore that any graph H which is Ramsey-equivalent to K_k must be the disjoint union of K_k and a graph without a K_k. Let mu(k,t) be the maximum m such that the graph H=K_k+m K_t, consisting of K_k and m disjoint copies of K_t, is Ramsey- equivalent to K_k. Szabó et al. gave a lower bound on mu(k,t). We prove an upper bound on mu(k,t) which is roughly within a factor 2 of the lower bound. Furthermore, we study the dependency of s_r(K_k) on r and show that, under the condition that k is constant, s_r(K_k) has order of magnitude r^(2+o(1). We also give an upper bound on s_r(K_k) which is polynomial in both r and k, and we determine s_r(K_3) up to a factor of log r.

Die Dissertation besteht im Wesentlichen aus zwei Teilen, die unabhängig voneinander sind. Im ersten Teil befassen wir uns mit Orientierungsspielen, die unter anderem bereits von Aigner, Alon, Beck, Ben-Shimon, Bollobás, Krivelevich, Sudakov, Szabó und Tuza studiert wurden. Zwei Spieler, genannt OMaker und OBreaker, richten abwechselnd bisher ungerichtete Kanten des K_n, dem vollständigen Graphen auf n Knoten. OMaker gewinnt, wenn der resultierende Digraph (ein Turnier) eine gewisse, vorher bestimmte, Eigenschaft P besitzt. Andernfalls gewinnt OBreaker. Für ein gegebenes Turnier T_k auf k Knoten betrachten wir das Orientierungsturnierspiel Or(T_k), bei dem OMaker gewinnt, wenn das finale Turnier eine Kopie von T_k enthällt. Wir zeigen, dass OMaker dieses Spiel gewinnen kann, solange k< (2-o(1)) log_2 n, während OBreaker eine Gewinnstrategie hat, sobald k ungefähr die Größenordnung 4 log_2 n besitzt. Für die untere Schranke betrachten wir die Spielvariante, in der OMaker gewinnt, wenn der Digraph, der nur aus ihren gerichteten Kanten besteht, eine Kopie von T_k enthällt. Dieses Turnierspiel wurde bereits von Beck und Gebauer studiert, und unsere untere Schranke verbessert bisherige Ergebnisse um einen konstanten Faktor. Darüberhinaus ist sie für das Turnierspiel scharf, wie das Kriterium von Erdos und Selfridge impliziert. Das zweite Orientierungsspiel, das wir betrachten ist das ``Oriented-cycle game'', in dem OMaker gewinnt, falls das finale Turnier einen gerichteten Kreis enthällt. Kürzlich zeigten Ben-Shimon, Krivelevich und Sudakov, dass OMaker gewinnt, selbst wenn OBreaker bis zu n/2 Kanten in jeder Runde richten darf. Sei b die Anzahl der Kanten, die OBreaker in einer Runde richten darf. Wie schon Bollobás und Szabó beobachteten, gewinnt OBreaker sobald b> n-3. Wir verbessern die triviale obere Schranke und zeigen, dass OBreaker eine Gewinnstrategie hat, wenn b> 5n/6 +1. Weiterhin passen wir die Strategie an für den Fall, dass OBreaker genau b Kanten in jeder Runde richten muss und widerlegen somit eine Vermutung von Bollobás und Szabó. Im zweiten Teil studieren wir minimale Ramseygraphen. Dabei ist ein Graph G Ramsey für einen Graphen H, falls jede Zweifärbung der Kanten von G eine einfarbige Kopie von H enthällt. Der Graph G wird dann Ramsey-minimal genannt, falls er Ramsey für H ist, aber kein echter Untergraph von G diese Eigenschaft besitzt. Sei s(H) der kleinste Minimalgrad, den ein Graph G haben kann, der Ramsey-minimal für H ist. Dieser Parameter wurde erstmals von Burr, Erdos, und Lovász studiert, die zeigten, dass s(K_k)=(k-1)^2. In dieser Arbeit beantworten wir eine Frage von Szabó, Zumstein, und Zürcher und zeigen, dass s(K_k . K_2)=k-1, wobei K_k . K_2 der Graph auf k+1 Knoten ist, bestehend aus einem K_k und einer angehängten Kante. Dieses Resultat impliziert interessanterweise, im Zusammenspiel mit einem bekannten Resultat von Nesetril und Rödl, dass jeder Graph, der Ramsey- äquivalent zu K_k ist, die disjunkte Vereinigung von K_k und einem Graph ohne K_k sein muss. Wir studieren die maximale Anzahl an Cliquen K_t, die zu K_k hinzugefügt werden können, sodass der resultierende Graph Ramsey-äquivalent zu K_k ist. Eine obere Schranke, die wir erhalten, ist ungefähr um einen Faktor zwei größer als eine untere Schranke von Szabó et al. Weiterhin verallgemeinern wir die Konzepte für r Farben und betrachten das Verhalten des entsprechenden Paramenters s_r(K_k) in Abhängigkeit von r. Unsere Schranken sind scharf bis auf einen Faktor, der polylogarithmisch in r ist.