| Phasenübergänge in Zufallsbäumen und Zufallsgraphen |
TUB Systematik
Abstract in English
We consider phase transitions in random graphs with constant
average degree, like
the sudden appearance of the giant component
or the giant k-core [2]
at some critical average degree.
Small neighbourhoods in such random graphs closely resemble
branching trees.
Frequently, the exact numerical values of the
critical average degrees and the expected sizes of the aforementioned
giant subgraphs can be
`predicted' in a semi-heuristic
manner from studying `corresponding' branching trees instead, which is
far simpler than the rigorous analysis of the phase transition
in the random graphs.
It is a major goal to turn this observation,
which - following [2] -
we shall call the `Branching Tree Connection',
into a rigorous proof technique. Goerdt and Molloy have
achieved this for the k-core in the model of random faulty configurations
in [1]. Abstract in Deutsch
Gegenstand unserer Untersuchungen sind Phasenübergänge in dünnen
Zufallsgraphen mit konstantem durchschnittlichen Grad c. Man spricht
von einem kombinatorischen Phasenübergang, wenn sich die Wahrscheinlichkeit
einer Grapheigenschaft als Funktion von c an einem *kritischen Wert*
asymptotisch unstetig verändert.
We prove
the sudden appearance of a giant subgraph that is
`almost the k-core', its
size being sharply concentrated around
what is predicted by the Branching
Tree Connection. Our proof, based on
the Principle of Deferred Decisions and a new application
of the Simple Concentration Bound, essentially employs the same recursive
equations as used for analysing a `corresponding' phase transition
in branching trees, thus providing structural
insight into why the Branching Tree Connection predicts
the correct values.
Adapting ideas from [1],
we show that the aforementioned subgraph which is
`almost the k-core' can be `purged',
yielding a giant k-core upon deletion of only o(n) nodes.
Motivated by a new phase transition phenomenon in
branching trees we have found a novel subgraph of k-partite
graphs, the magic subgraph. We can empirically
demonstrate its sudden appearance. Both critical average degree
and size are in good accordance with the
Branching Tree Connection.
The fact that it appears at a critical average degree of
4.91... suggests a relation with
the Antivoter Phenomenon~([3]).
Moreover, when it appears, the
magic subgraph seems to
be `almost uniquely k-colourable', which may turn out to be
relevant for understanding the threshold for k-colourability
in non-k-partite random graphs with constant average degree.
[1] Goerdt/Molloy, Analysis of edge deletion processes on faulty random
regular graphs, Proceedings Latin 2000, pp. 38-47, 2000.
[2] Pittel/Spencer/Wormald, Sudden emergence of a giant k-core in a random
graph, Journal of Combinatorial Theory Series B (67), pp. 111-151, 1996.
[3] Petford/Welsh, A randomised 3-colouring algorithm,
Discrete Mathematics (74), pp. 253-261, 1989.
So hat etwa die Eigenschaft von Graphen, dreifärbbar zu sein, einen
solchen Phasenübergang. Dreifärbbarkeit zu entscheiden ist ein
kanonisches NP-vollständiges Problem, und die Analyse des Phasenubergangs,
insbesondere die exakte Bestimmung des kritischen Wertes, ist Gegenstand
vieler
aktueller Forschungsbemühungen.
Dünne Zufallsgraphen ähneln lokal zufälligen Bäumen (Branching Trees) mit
durchschnittlicher Kinderzahl c. In Branching Trees gibt es
`korrespondierende'
Phasenübergänge, die wegen der Unabhängigkeit von Teilbäumen relativ leicht
zu
analysieren sind. Nun koinzidieren in mehreren Fällen die kritischen Werte,
die aus der Betrachtung der Branching Trees stammen, mit den entsprechenden
Werten, die man mit ungleich größerem Aufwand für Zufallsgraphen beweisen
kann.
Diese Beobachtung diente bisher allein einer *heuristischen* Erklärung des
Phasenübergangs im Zufallsgraphen.
Die Arbeit enthält eine neue Beweistechnik für Phasenübergänge in dünnen
Zufallsgraphen, welche die Analyse des `korrespondierenden' Phasenübergangs
in Branching Trees weitgehend nachahmt, ohne jedoch die in Zufallsgraphen
vorhandenen Abhängigkeiten zu vernachlässigen. In Kombination
mit Ideen aus [1] konnten wir damit den Beweis in [2] für das plötzliche
Auftauchen eines linear großen Subgraphen mit minimalem Grad k bei
c=3.35... deutlich vereinfachen.
Weiterhin haben wir einen neuartigen Phasenübergang in tripartiten
Zufallsgraphen mit durchschnittlichen Grad c erstmals beschrieben und
analysiert. Bei einem kritischen Wert von c=4.91... taucht plötzlich ein
linear großer Subgraph mit gewissen Eigenschaften auf, was intuitiv eine
plötzliche `Versteifung' gegenüber lokalen Umfärbungen bedingt. Dieses
Phänomen verdient besonderes Interesse angesichts der empirisch
beobachteten Lauzeitdivergenz einer randomisierten lokalen Färbungs-
heuristik [3] auf tripartiten Zufallsgraphen bei einem durchschittlichen
Grad nahe bei fünf.
[1] Goerdt/Molloy, Analysis of edge deletion processes on faulty random
regular graphs, Proceedings Latin 2000, pp. 38-47, 2000.
[2] Pittel/Spencer/Wormald, Sudden emergence of a giant k-core in a random
graph, Journal of Combinatorial Theory Series B (67), pp. 111-151, 1996.
[3] Petford/Welsh, A randomised 3-colouring algorithm,
Discrete Mathematics (74), pp. 253-261, 1989.
| Betreuer | Steger, A.; Prof. Dr. |
| Gutachter | Steger, A.; Prof. Dr. |
| Gutachter | Goerdt, A.; Prof. Dr. (TU Chemnitz) |
| Upload: | 2002-02-25 |
| URL of Theses: | http://tumb1.biblio.tu-muenchen.de/publ/diss/in/2002/voll.pdf |
Unversehrtheit der Publikation