Ramsey and Universality Properties of Random - ETH E

Diss. ETH No. 23559
Ramsey and Universality
Properties of Random Graphs
A thesis submitted to attain the degree of
DOCTOR OF SCIENCES of ETH Zurich
(Dr. sc. ETH Zurich)
presented by
Rajko Nenadov
Master of Science ETH in Computer Science
born on 14.11.1987
citizen of Serbia
accepted on the recommendation of
Prof. Dr. Angelika Steger, examiner
Prof. Dr. Michael Krivelevich, co-examiner
2016
Abstract
This thesis investigates the interplay between two branches of discrete
mathematics: Ramsey theory and random graphs.
The origins of Ramsey theory can already be found in the work of Hilbert
from the early 20th century. However, it was a simple but profound result of Frank P. Ramsey from 1930 which marked the beginning of the
new field in mathematics. Phrased in graph theory terms, Ramsey’s
theorem states that for every `-uniform hypergraph H and sufficiently
(`)
large complete `-uniform hypergraph Kn , no matter how one colours
(`)
the edges of Kn with two colours there will always exist a monochromatic copy of H, that is a copy of H with all edges having the same
(`)
colour. For short, we say that such Kn is Ramsey for H. Many variations of the Ramsey property have been studied since then. Generally
speaking, we will use the term Ramsey-type property as an umbrella
term for any such property involving colourings.
Even though it might appear as a naive statement at first, Ramsey’s
theorem gave rise to a whole new field with far-reaching results. Perhaps even more important, many techniques and ideas that are now
considered to be standard tools in the arsenal of a mathematician have
been developed in order to tackle questions in Ramsey theory. Thus it
is a fruitful playground whose problems serve as benchmarks for ideas.
iii
iv
Abstract
Various questions derived from Ramsey’s theorem continue to challenge
mathematicians.
The study of random graphs started with the seminal work of Erdős and
Rényi from 1959. Rather than just being interesting structures on their
own, it turned out that some of the best possible (or best known) constructions of graphs with certain properties stem from random graphs.
This twofold view on random graphs is also present here: in the first
part of the thesis we study random graphs for their own sake, while
in the second part we use them to construct sparse graphs which are
Ramsey for a special family of graphs.
We consider the binomial random graph model G(n, p). Given a parameter p ∈ [0, 1], a random graph G ∼ G(n, p) on n vertices is generated by
simply including each possible edge with probability p, independently.
Bollobás and Thomason showed that random graphs exhibit a rather
peculiar phenomenon: given a monotone increasing graph property P
(i.e. a property which is preserved under edge addition) there exists a
function p0 = p0 (n) such that if p p0 (resp. p p0 ) then G(n, p) has
the property P with probability tending to 1 (resp. 0) as n goes to infinity. In other words, random graphs exhibit threshold behaviour with
respect to monotone properties. For example, P can be the property
of being connected, containing a Hamilton cycle, etc. The typical problem in random graph theory is thus to determine such a function for a
chosen property. We make a small contribution towards understanding
thresholds for Ramsey-type properties in random graphs.
In the first part of the thesis we build upon a classic theorem of Rödl
and Ruciński which determines the threshold for the property of being
Ramsey for a graph H. Our first contribution is a short proof of the
upper bound on the threshold in the Rödl-Ruciński Theorem using the
so-called hypergraph containers method developed by Balogh, Morris
and Samotij and independently by Saxton and Thomason. Taking into
account that we use heavy machinery, this is a rather humble contribution. Nonetheless, it has both educational and research characters:
our proof has appeared in the recent monograph on random graphs by
Frieze and Karoński and the ideas of the proof were further utilised by
other groups of authors.
Our second contribution is a unifying approach for proving lower bounds
on thresholds for various Ramsey-type properties. In particular, we
develop a framework which reduces the problem of showing that G(n, p)
does not have a Ramsey-type property to showing that graphs with
Abstract
v
certain local density conditions do not have such a property. In other
words, we reduce the probabilistic question to a deterministic one. This
approach is then demonstrated to obtain a lower bound for the Ramsey
property (reproving the Rödl-Ruciński Theorem), anti-Ramsey property
for r-bounded colourings and proper colourings, and the Maker-Breaker
H-game.
In the second part of the thesis we study size Ramsey numbers of graphs
with constant maximum degree, a class of graphs that has recently
attracted considerable attention in the theory of random graphs. Size
Ramsey number of H, denoted by r̂(H), is defined as the smallest m ∈ N
such that there exists a graph G with m edges which is Ramsey for H.
Given a graph H with maximum degree at most some constant ∆, it is
of interest to determine the order of r̂(H). On the one hand, Rödl and
Szemerédi showed that for every sufficiently large n there exists a 3regular graph H such that r̂(H) ≥ n logc n for some constant c > 0. On
the other hand, the result of Rödl, Kohayakawa, Szemerédi and Schacht
shows that there exists a constant C > 0 such that
r̂(H) ≤ Cn2−1/∆ log1/∆ n
for every graph H with n vertices and maximum degree ∆. This leaves
a gap between the two bounds. We give a polynomial improvement of
the upper bound in the case where H is triangle-free. This includes,
among others, bipartite graphs. Similarly to Rödl et al. we use random
graphs to find a witness for r̂(H). There is evidence that in some cases
the bound we obtain is close to the best possible using random graphs.
It turns out that our proof on the upper bound on r̂(H) actually implies
a stronger statement. In particular, we show that there exists a graph
G with n2−1/∆−α edges, for some α = α(∆) > 0, such that for every
colouring of the edges of G one of the colours contains every graph with
at most n vertices and maximum degree at most ∆. In other words, one
of the colours is universal for such a family of graphs. Therefore, as a
warm-up, we first consider the question of finding the threshold for the
property that G(n, p) is universal for graphs with bounded maximum
degree. Improving upon the result of Alon, Capalbo, Kohayakawa, Rödl,
Ruciński and Szemerédi, we determine (up to the logarithmic factor) the
threshold for such property when ∆ = 3 and give the best known upper
bound in case ∆ > 3. Ideas developed for this problem are then reused
to improve the size Ramsey number.
Zusammenfassung
Ursprünge der Ramsey-Theorie können bereits in der Arbeit von Hilbert aus dem frühen 20. Jahrhundert gefunden werden. Es war jedoch
ein einfaches, aber tiefes Ergebnis von Frank P. Ramsey aus dem Jahr
1930, das den Beginn des neuen Feldes in der Mathematik markiert. In
die Sprache der Graphentheorie übersetzt besagt der Satz von Ramsey
dass für jeden `-uniformen Hypergraphen H und hinreichend grossen
und vollständigen `-uniformen Hypergraphen Kn` , jede 2-Färbung der
Kanten von Kn` eine einfarbige Kopie von H enthält. Kurz gesagt Kn` ist
Ramsey für H. Viele Variationen der Ramsey-Eigenschaft wurden seitdem untersucht. Generell werden wir den Begriff Ramsey-Eigenschaft
als Oberbegriff für eine solche Eigenschaft jeder Färbung verwenden.
Auch wenn es zunächst als naive Aussage erscheinen mag, enstand mit
dem Satz von Ramsey ein ganz neues Feld mit weitreichenden Ergebnissen. Von vielleicht noch grösserer Bedeutung sind viele Techniken
und Ideen, die nun Standard-Methoden im Arsenal eines Mathematikers sind, und die im Zusammenhang mit Problemen aus der RamseyTheorie entwickelt wurden. Das heisst Ramsey-Theorie ist ein Spielplatz, dessen Probleme als Massstab für neue Ideen dienen. Verschiedene Fragen, die aus dem Satz von Ramsey abgeleitet sind, fordern
Mathematiker weiterhin heraus.
vii
viii
Zusammenfassung
Die Untersuchung von Zufallsgraphen begann mit der bahnbrechenden
Arbeit von Erdős und Rényi von 1959. Zufallsgraphen sind nicht nur
intrinsisch interessant. Es stellte sich heraus, dass einige der besten
Konstruktionen von Graphen mit bestimmten Eigenschaften von Zufallsgraphen stammen. Diese doppelte Ansicht auf Zufallsgraphen wird
auch hier präsentiert: Im ersten Teil der Arbeit untersuchen wir Zufallsgraphen um ihrer selbst willen, während wir sie im zweiten Teil benutzen, um dünne Graphen zu konstruieren, die Ramsey für eine gewisse
Familie von Graphen sind.
Wir betrachten das binomische Zufallsgraphen-Modell. Für einen Parameter p ∈ [0, 1] wird ein Zufallsgraph G ∼ G(n, p) auf n Knoten
erzeugt, indem jede mögliche Kante mit Wahrscheinlichkeit p existiert,
wobei alle Kanten unabhängig gewählt werden. Bollobás und Thomason
zeigten, dass Zufallsgraphen sehr spezielle Erscheinung besitzen: Es sei
P eine monoton steigende Grapheneigenschaft, das heisst eine Eigenschaft, die unter Hinzufügen von Kanten erhalten bleibt. Bollobás und
Thomason zeigten, dass dann eine Funktion p0 = p0 (n) existiert so dass
G(n, p) die Eigenschaft P mit einer Wahrscheinlichkeit besitzt, die für
p p0 (p p0 ) gegen 1 (0) geht, wenn n → ∞. Mit anderen Worten,
Zufallsgraphen zeigen ein Schwellenverhalten in Bezug auf monotone
Eigenschaften. Zum Beispiel kann P die Eigenschaft sein zusammenhängend zu sein; einen Hamiltonkreis zu enthalten, usw. Das typische
Problem in der Zufallsgraphentheorie ist für eine gegebene Eigenschaft
eine solche Funktion zu bestimmen. Wir machen einen kleinen Beitrag
zum Verständnis einiger Schwellenwerte für Ramsey-Eigenschaften in
Zufallsgraphen.
Im ersten Teil der Arbeit betrachten wir einen klassischen Satz von Rödl
und Ruciński, der den Schwellenwert für die Eigenschaft Ramsey für
einen gegebenen Graph H bestimmt. Unser erster Beitrag ist ein kurzer
Beweis für die obere Schranke an den Schwellenwert im Rödl-Ruciński
Satz mit Hilfe der so genannten Hypergraph-Container-Methode, entwickelt von Balogh, Morris und Samotij und unabhängig von Saxton
und Thomason. Auch wenn wir hier schwere Maschinerie verwenden, so
hat dies sowohl Bildungs- als auch Forschungswert: Unser Beweis ist in
der jüngsten Monographie über Zufallsgraphen von Frieze und Karoński erschienen und die Ideen des Beweises wurden weiter durch andere
Gruppen von Autoren genutzt.
Unser zweiter Beitrag ist ein verbindender Ansatz für den Nachweis
der unteren Grenzen für Schwellenwerte für verschiedene Ramsey Ei-
Zusammenfassung
ix
genschaften. Insbesondere entwickeln wir einen Rahmen, der das Problem, zu zeigen dass G(n, p) keine Ramsey-Eigenschaft hat, auf das Problem reduziert zu zeigen, dass Graphen mit bestimmten lokalen DichteBedingungen nicht eine solche Eigenschaft haben. Mit anderen Worten,
wir reduzieren die probabilistische Frage zu einer deterministischen. Dieser Ansatz wird dann genutzt, um verschiedene weitere Resultate zu
erhalten.
Im zweiten Teil der Arbeit untersuchen wir size-Ramsey-Zahlen von
Graphen mit konstantem Maximalgrad, eine Klasse von Graphen, die
vor kurzem grosse Beachtung in der Theorie der Zufallsgraphen fand.
Die size-Ramsey-Zahl von H bezeichnet durch r̂(H), ist die kleinste natürliche Zahl m ∈ N, so dass es einen Graphen G mit m Kanten gibt, der
Ramsey für H ist. Sei H ein Graph mit Maximalgrad höchstens ∆, wobei
∆ eine Konstante ist, so wollen wir die Grösse von r̂(H) bestimmen. Auf
der einen Seite zeigten Rödl und Szemerédi, dass für jedes hinreichend
grosse n ein 3-regulärer-Graph H existiert, so dass r̂(H) ≥ n logc n für
eine Konstante c > 0. Auf der anderen Seite zeigten Rödl, Kohayakawa,
Szemerédi und Schacht, dass es eine Konstante C > 0 gibt, so dass
r̂(H) ≤ Cn2−1/∆ log1/∆ n
für jeden Graphen H mit n Knoten und Maximalgrad ∆. Dies hinterlässt
eine beträchtliche Lücke. Wir geben eine polynomielle Verbesserung der
oberen Schranke an, für den Fall, dass der Graph H dreiecksfrei ist. Dies
deckt unter anderem den Fall der bipartiten Graphen ab. Ähnlich wie
bei Rödl et al. verwenden wir Zufallsgraphen um einen Zeugen für r̂(H)
zu finden. Es ist erwiesen, dass in einigen Fällen die Schranke, die wir
erhalten, in der Nähe der bestmöglichen Verwendung von Zufallsgraphen
ist.
Es stellt sich heraus, dass unser Beweis an der oberen Grenze für r̂(H)
tatsächlich eine starke Aussage impliziert. Insbesondere zeigen wir, dass
ein Graph G existiert mit n2−1/∆−α Kanten, für ein α = α(∆) > 0, so
dass für jede Färbung der Kanten von G eine der Farben jeden Graphen
mit höchstens n Knoten und Maximalgrad höchstens ∆ enthält. Mit
anderen Worten: eine der Farben ist universal für eine solche Familie
von Graphen.
Als nächstes betrachten wir daher das Problem, die Schwellenwerte für
die Eigenschaft zu finden, dass G(n, p) universal für Graphen mit beschränktem Maximalgrad ist. Wir verbessern ein Ergebnis von Alon,
Capalbo, Kohayakawa, Rödl, Ruciński und Szemerédi, indem wir den
x
Zusammenfassung
Schwellenwert für eine solche Eigenschaft bestimmen (bis auf einen logarithmischen Faktor) für ∆ = 3 und geben die beste bekannte obere
Schranke im Fall ∆ > 3. Ideen aus diesem Beweis werden dann verwendet, um die size-Ramsey-Zahl zu verbessern.

Download Report