The phase transition in random graphs and random graph processes [Elektronische Ressource] / von Taral Guldahl Seierstad

Seierstad Taral Guldahl

Sujets

• Mathematics

Informations

• Publié par: humboldt-universitat_zu_berlin
• Publié le: 01 janvier 2007
• Nombre de lectures: 14
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

The phase transition in random graphs and
random graph processes
DISSERTATION
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften (doctor rerum naturalium)
im Fach Informatik
eingereicht an der
Mathematisch-Naturwissenschaftlichen Fakultät II
der Humboldt-Universität zu Berlin
von
Herr cand.scient. Taral Guldahl Seierstad
geboren am 5. September 1979 in Lillehammer
Präsident der Humboldt-Universität zu Berlin:
Prof. Dr. Christoph Markschies
Dekan der Mathematisch-Naturwissenschaftlichen Fakultät II:
Prof. Dr. Wolfgang Coy
Gutachter:
1. Prof. Dr. Hans Jürgen Prömel
2. Prof. Dr. Tomasz Łuczak
3. Prof. Dr. Stefan Felsner
eingereicht am: 29. Januar 2007
Tag der mündlichen Prüfung: 28. Juni 2007Zusammenfassung
Zufallsgraphen sind Graphen, die durch einen zufälligen Prozess erzeugt
werden.EinimZusammenhangmitZufallsgraphenhäufigauftretendesPhäno-
men ist, dass sich die typischen Eigenschaften eines Graphen durch Hinzu-
fügen einer relativ kleinen Anzahl von zufälligen Kanten radikal verändern.
Dieses Phänomen wurde zuerst in den bahnbrechenden Arbeiten von Erdős
und Rényi untersucht.
Wir betrachten den Zufallsgraphen G(n,p), dern Knoten enthält und in
dem zwei Knoten unabhängig und mit Wahrscheinlichkeitp durch eine Kante
cverbunden sind. Erdős und Rényi zeigten, dass ein Graph für p = und
n
c< 1 mit hoher Wahrscheinlichkeit aus Komponenten mit O(logn) Knoten
cbesteht. Für p = und c > 1 enthält G(n,p) mit hoher Wahrscheinlichkeit
n
genau eine Komponente mit Θ(n) Knoten, welche viel größer als alle anderen
Komponenten ist.
Der Punkt in der Entwicklung des Graphen, an dem sich die Kompo-
nentenstruktur durch eine kleine Erhöhung der Anzahl von Kanten stark
1verändert, wird Phasenübergang genannt. Im G(n,p) passiert er bei p = .
n
Darüber hinaus durchlebt G(n,p) einen sogenannten Doppelsprung. Wenn
1−ε 1die Wahrscheinlichkeit p von auf steigt, dann wächst die größte Kom-
n n
2/3 1+εponente von O(logn) auf Θ(n ) Knoten. Ist schließlich p gleich , dann
n
1+εbesteht die größte Komponente aus Θ(n) Knoten. Wenn p = , wobei
n
ε =ε(n) eine Funktion vonn ist, die gegen 0 geht, sind wir in der kritischen
Phase, welche eine der interessantesten Phasen der Entwicklung des Zufalls-
graphen ist. In diesem Fall hängt die Komponentenstruktur des Graphen von
der Geschwindigkeit ab, mit welcher ε gegen 0 konvergiert.
In dieser Arbeit betrachten wir drei verschiedene Modelle von Zufalls-
graphen. In Kapitel 4 studieren wir den Minimalgrad-Graphenprozess. In
diesem Prozess werden sukzessive Kanten vw hinzugefügt, wobei v ein zu-
fällig ausgewählter Knoten von minimalem Grad ist. Wir beweisen, dass es
in diesem Graphenprozess einen Phasenübergang und wie im G(n,p) einen
Doppelsprung gibt.
Die zwei anderen Modelle sind Zufallsgraphen mit einer vorgeschriebenen
Gradfolge und zufällige gerichtete Graphen. Für diese Modelle wurde bereits
in denArbeiten vonMolloy undReed (1995), Karp(1990) undŁuczak (1990)
gezeigt, dass es einen Phasenübergang bezüglich der Komponentenstruktur
gibt. In dieser Arbeit untersuchen wir in Kapitel 5 und 6 die kritische Phase
dieser Prozesse genauer und zeigen, dass sich diese Modelle ähnlich zum
G(n,p) verhalten.
Schlagwörter:
Zufallsgraphen, Phasenübergang, kritische Phase, größte KomponenteAbstract
Random graphs are graphs which are created by a random process. They
areusedamongotherplacesinthestudyoflargenetworks,andintheanalysis
of the performance of algorithms.
A common phenomenon in random graphs is that the typical properties
of a graph change radically by the addition of a relatively small number of
random edges. This phenomenon was first investigated in the seminal papers
of Erdős and Rényi.
We consider the graph G(n,p) which contains n vertices, and where any
two vertices are connected by an edge independently with probability p.
cErdős and Rényi showed that ifp = andc< 1, then with highy
n
cG(n,p) consists of components with O(logn) vertices. If p = and c > 1,
n
then with high probability G(n,p) contains exactly one component, called
the giant component, with Θ(n) vertices, which is much larger than all other
components.
The phase transition in a random graph refers to the point at which
1the giant component is formed. In G(n,p) this is when p = . Moreover,
n
G(n,p)undergoesaso-calleddouble jumpatthispoint. Whentheprobability
1−ε 1p increases from to , the largest component grows from O(logn) to
n n
1+ε2/3Θ(n ) vertices. Whenp becomes , thegraph containsa giant component
n
1+εwith Θ(n) vertices. If we let p = , where ε is a function of n tending to
n
0, we are in the critical phase of the random graph, which is one of the most
interesting phases in the evolution of the random graph. In this case the
structure depends on how fast ε tends to 0.
In this dissertation we consider three different random graph models. In
Chapter 4 we consider the so-called minimum degree graph process. In this
process edgesvw are added successively, wherev is a randomly chosen vertex
with minimum degree. We prove that a phase transition occurs in this graph
process as well, and also that it undergoes a double jump, similar toG(n,p).
The two other models we will consider, are random graphs with a given
degreesequenceandrandomdirectedgraphs. Inthesemodelsthepointofthe
phase transition has already been found, by Molloy and Reed (1995), Karp
(1990) and Łuczak (1990). In Chapter 5 and 6 we investigate the critical
phase of these processes, and show that their behaviour resembles G(n,p).
Keywords:
random graphs, phase transition, critical phase, giant componentAcknowledgement
I would like to thank my supervisor Prof. Dr. Hans Jürgen Prömel for letting
me join his research group at the Humboldt University, and the European
Graduate Program “Combinatorics, Geometry, and Computation” for schol-
arship and support. I also want to thank the members of the research group
for algorithms and complexity at the Humboldt University for interesting
discussions and seminars, especially Prof. Dr. Anusch Taraz who helped me
much during my first year, and Dr. Mihyun Kang with whom I have had
many stimulating discussions.
Furthermore I want to thank Dr. Manuel Bodirsky who gave me feed-
back on a draft of this dissertation. I am also grateful to Prof. Dr. Michał
Karoński and the members of the Department for Discrete Mathematics at
the Adam Mickiewicz University for their hospitality, and in particular to
Prof. Dr. Tomasz Łuczak for very inspiring collaboration, and to Dr. Mał-
gorzataBednarskawhowasveryhelpfulduringmysix-monthstayinPoznań.
Finally I want to thank my family for their support and encouragement
through many years.
vPreface
In this thesis we study the evolution of random graph processes. The study
ofrandomgraphswasinitiatedbyErdősandRényiaround1960, andbecame
a flourishing research area in the following decades. We will mostly concern
ourselves with a phenomenon which occurs in several random graph pro-
cesses, generally known as the phase transition, namely that the component
structure of a random graph changes substantially caused by the addition of
relatively few edges.
One of the motivations for studying random graphs is the desire to de-
scribe a “typical” graph. For example, if we consider all labelled graphs on
nvertices, itisknownthatthevastmajorityofthegraphsareconnected, con-
ntain a copy of any fixed graph F, and has chromatic number close to ,
2log n2
provided that n is large enough. Moreover, the proportion of graphs not
having these properties decreases as n grows. We therefore feel justified in
saying that “almost all” graphs have these properties. In the terminology
of random graphs we say that a random graph has these properties with
probability tending to 1 as the number of vertices tends to infinity.
More interesting results can be obtained if we restrict ourselves to sub-
classes of graphs, for example by fixing the number of edges and asking what
the typical properties of a graph with n vertices and m edges are. Often
we think of random graphs as states in a process. We begin at time 0 with
an empty graph on n vertices. Then as the time goes, we add edges to the
graphs at random, either uniformly or according to some other random pro-
cedure. A discovery of Erdős and Rényi was that many graph properties
enjoy so-called threshold phenomena: when the number of edges in the ran-
dom graph is significantly smaller than the threshold, it has the property
with probability very close to 0, while if the number of edges is significantly
greater than the threshold, it has the property with probability very close
to 1.
The main topic of this dissertation is the phenomenon known as the
phase transition. A random graph with n vertices and 0.49n edges is very
likely to consist of many small components, none of which has more than
vivii
O(logn) vertices, while a random graph with n vertices and 0.51n edges
most probably contains a unique large component contai