On extremal properties of minimal Ramsey graphs and cross intersecting families

Abstract

Diese Arbeit ist in vier Teile gegliedert, von denen drei das Verhalten der Menge der minimalen Ramsey-Graphen für einen bestimmten Graphen untersuchen. Im ersten Teil untersuchen wir das Phänomen der Ramsey-simplicity für Zufallsgraphen Gn,p. Wir zeigen die Existenz eines Schwellenwertes für die Anzahl der Farben, für die ein gegebener Graph Ramsey-simple ist, und bestimmen verschiedene Schranken dafür. Im zweiten Teil de nieren und analysieren wir die abundance von Graphen. Wir präsentieren viele un endliche Klassen von Graphen, die für eine bestimmte Anzahl von Farben abundant sind. Der dritte Teil der Arbeit liefert einen Beweis für asymmetrische Paare von Graphen, die Ramsey-äquivalent zueinander sind. Im letzten Teil dieser Arbeit bestimmen wir die max imale Summe der Gröÿen auf r-cross t-intersecting families in verschiedenen Situationen.

This thesis is divided into four parts, three out of which investigate the behaviour of the set of minimal Ramsey graphs for a particular graph. In the rst part we investigate the phenomena of Ramsey simplicity for random graphs, Gn,p. We show the existence of a threshold value for the number of colours for which a given graph is Ramsey simple and determine various bounds for it. In the second part we de ne and analyse the abundance properties of graphs. We exhibit many in nite classes of graphs which are abundant for a certain number of colours. The third part of the thesis provides an evidence of asymmetric pairs of graphs which are Ramsey equivalent. In the last part of this thesis we determine the maximum sum of the sizes of r-cross t-intersecting families in various settings.