05C80 Random graphs [See also 60B20]
Refine
Document Type
- diplomthesis (2)
- Article (1)
Has Fulltext
- yes (3)
Is part of the Bibliography
- no (3)
Keywords
- Assignment Problem (1)
- Diskreter Markov-Prozess (1)
- Erwartungswert (1)
- Kombinatorische Optimierung (1)
- Kontaktprozess (1)
- Parisi conjecture (1)
- Small Worlds (1)
- Stochastischer Prozess (1)
- Varianz (1)
- Verzweigungsprozess (1)
Institute
- Mathematik (3)
In the model of randomly perturbed graphs we consider the union of a deterministic graph G with minimum degree αn and the binomial random graph G(n, p). This model was introduced by Bohman, Frieze, and Martin and for Hamilton cycles their result bridges the gap between Dirac’s theorem and the results by Pósa and Korshunov on the threshold in G(n, p). In this note we extend this result in G ∪G(n, p) to sparser graphs with α = o(1). More precisely, for any ε > 0 and α: N ↦→ (0, 1) we show that a.a.s. G ∪ G(n, β/n) is Hamiltonian, where β = −(6 + ε) log(α). If α > 0 is a fixed constant this gives the aforementioned result by Bohman, Frieze, and Martin and if α = O(1/n) the random part G(n, p) is sufficient for a Hamilton cycle. We also discuss embeddings of bounded degree trees and other spanning structures in this model, which lead to interesting questions on almost spanning embeddings into G(n, p).
Mit den Small World Graphen stehen seit Ende der Neunzigerjahre Modelle für soziale und ähnliche Netzwerke, die im Vergleich zu Erdös-Rényi-Graphen stärker Cluster ausbilden, zur Verfügung. Wir betrachten die Konstruktion dieser Graphen und untersuchen zwei der Modelle genauer im Zusammenhang mit stochastischen Prozessen. Das stetige Modell betrachten wir hinsichtlich dem Abstand zweier Knoten. Der interessanteste Aspekt hierbei ist, dass man bei der Konstruktion des Graphen die entfernten Nachbarn mithilfe der Poissonverteilung wählt und in der Folge einen Yule-Prozess auf dem Graphen erhält. Auf der Bollobás-Chung Small World lassen wir den Kontaktprozess ablaufen und untersuchen diesen bezüglich seiner Überlebenswahrscheinlichkeit. Wir sehen, dass er auf diesem Graphen zwei Phasenübergänge aufweist. Oberhalb des ersten überlebt er für immer mit positiver Wahrscheinlichkeit, oberhalb des zweiten ist zudem der Knoten, auf dem der Kontaktprozess gestartet ist, stets mit positiver Wahrscheinlichkeit infiziert. Schließlich betrachten wir die Zeitdauer, die ein leicht modifizierter, superkritischer Kontaktprozess auf der Small World unter bestimmten Voraussetzungen überlebt. Die wesentliche Dynamik, die wir hierbei ausmachen können, ist, dass auf ein Absinken der Infektionen mit hoher Wahrscheinlichkeit wieder eine Verdopplung der Infektionen folgt.
Das Assignment Problem ist ein bekanntes kombinatorisches Optimierungsproblem, bei dem es darum geht, in einem gewichteten bipartiten Graphen ein Matching mit minimalem Gewicht zu finden. In dieser Arbeit sind die Kantengewichte exponentialverteilt zu speziell gewählten Raten. Damit sind Erwartungswert und Varianz des minimalen Gewichts von besonderem Interesse. Zunächst wird ein Beweis der Parisi Formel und der Coppersmith-Sorkin Formel erläutert. Die Formeln beschreiben den Erwartungswert des minimalen Gewichts im Fall, dass die Raten alle dem Wert 1 entsprechen. Im zweiten Teil wird die Herleitung einer expliziten Formel zur Berechnung der Varianz des zufälligen minimalen Gewichts erklärt, wobei die Raten immer noch mit 1 übereinstimmen. Gleichzeitig wird eine Formel für die höheren Momente geliefert, aus der die Parisi Formel und Coppersmith-Sorkin Formel aus dem ersten Teil folgen und die sogar das bisherige Modell bezüglich der Parameter erweitert. Schließlich kann man das Ergebnis des zweiten Teils zur Beschreibung des asymptotischen Verhaltens der Varianz benutzen.