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]. 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.     «

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...     »

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. 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.     «

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. 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...     »