Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > de.sci.mathematik > #143789 > unrolled thread

Heute vor 33 Jahren

Back to article view | Back to de.sci.mathematik

Contents

  Heute vor 33 Jahren ram@zedat.fu-berlin.de (Stefan Ram) - 2026-07-08 11:02 +0000
    Re: Heute vor 33 Jahren Joachim Pimiskern <JoachimPimiskern@web.de> - 2026-07-09 13:09 +0200
      Re: Heute vor 33 Jahren ram@zedat.fu-berlin.de (Stefan Ram) - 2026-07-09 13:05 +0000
      Re: Heute vor 33 Jahren ram@zedat.fu-berlin.de (Stefan Ram) - 2026-09-30 20:05 +0000

#143789 — Heute vor 33 Jahren

  Heute vor 33 Jahren hörte ich Donald Knuth, der am 1993-07-09
  zu Gast im Berliner Mathematischen Kolloquium war, über
  "The Birth of A Giant Component" sprechen

  Ich weiß nicht, wieviel ich damals von dieser Arbeit Knuths
  verstanden hatte. Ich glaube, daß mir das Verständnis durch die
  viele Details des Vortrags erschwert wurde, während der Chatbot heute
  die Arbeit aus der Vogelperspektive übersichtlich schildern kann.

| "The Birth of the Giant Component" ist eine bahnbrechende
| mathematische Arbeit aus dem Jahr 1993, die im Journal Random
| Structures & Algorithms veröffentlicht wurde. Zusammen mit Svante
| Janson, Tomasz Łuczak und Boris Pittel liefert Donald Knuth hier eine
| exakte Analyse eines Phasenübergangs in zufälligen Graphen. Knuth
| bezeichnete diese Arbeit oft als die mathematische Leistung, auf die
| er am stolzesten ist.
| 
| Der Kern der Arbeit befaßt sich mit folgenden Konzepten:
| 
| Der Phasenübergang (Die Schwelle)
| 
| Die Ausgangslage   Das Paper analysiert das klassische
| Erdős-Rényi-Modell für Zufallsgraphen. Man startet mit n isolierten
| Punkten (Knoten) und fügt nacheinander zufällige Linien (Kanten)
| hinzu.
| 
| Die magische Grenze   Ein dramatischer Sprung passiert, wenn die
| Anzahl der Kanten genau die Hälfte der Knotenanzahl erreicht (n/2).
| 
| Vor der Schwelle   Bei weniger als n/2 Kanten besteht der Graph nur
| aus vielen kleinen, isolierten Clustern.
| 
| Nach der Schwelle   Sobald die Grenze überschritten wird, verschmelzen
| diese Cluster schlagartig zu einer einzigen "Riesenkomponente" (Giant
| Component), die den Großteil des Netzwerks verbindet.
| 
| Mathematische Kernergebnisse
| 
| Struktur der Komponenten   Die Autoren bewiesen exakt, welche
| Strukturen direkt am kritischen Übergangspunkt existieren. Der Graph
| besteht dort fast nur aus einfachen Bäumen sowie Clustern mit maximal
| ein oder zwei Schleifen (Zyklen).
| 
| Entstehung des Chaos   Die Arbeit zeigt über einen Markov-Prozeß, wie
| komplexe Strukturen wachsen und wie der plötzliche Übergang von
| Ordnung zu dichter Vernetzung abläuft.
| 
| Exakte Wahrscheinlichkeit   Sie berechneten die exakte
| Grenzwahrscheinlichkeit von rund 93,25 %, daß ein Zufallsgraph an
| dieser Schwelle nur aus diesen einfachen, dünn besiedelten Strukturen
| besteht.
| 
| Warum das wichtig ist
| 
| Diese mathematische Arbeit erklärt, wie Vernetzung in der echten Welt
| funktioniert. Die Formeln werden heute genutzt, um die Ausbreitung von
| Epidemien, die Stabilität des Internets, soziale Netzwerke oder
| Phasenübergänge in der Physik zu erforschen.

[toc] | [next] | [standalone]

#143791

Am 08.07.2026 um 13:02 schrieb Stefan Ram:

 > Nach der Schwelle   Sobald die Grenze überschritten wird,
 > verschmelzen diese Cluster schlagartig zu einer einzigen
 > "Riesenkomponente" (Giant Component), die den Großteil
 > des Netzwerks verbindet.

Das erinnert mich an den Begriff Perkolation.

Grüße,
Joachim

[toc] | [prev] | [next] | [standalone]

#143792

Joachim Pimiskern <JoachimPimiskern@web.de> schrieb oder zitierte:
>Am 08.07.2026 um 13:02 schrieb Stefan Ram:
>>Nach der Schwelle   Sobald die Grenze überschritten wird,
>>verschmelzen diese Cluster schlagartig zu einer einzigen
>>"Riesenkomponente" (Giant Component), die den Großteil
>>des Netzwerks verbindet.
>Das erinnert mich an den Begriff Perkolation.

  Es gibt tatsächlich Ähnlichkeiten mit der Perkolationstheorie,
  die untersucht, ab wann lokale, zufällige Verbindungen kleinerer
  Einheiten ein großes, zusammenhängendes System bilden. In beiden
  Fällen gibt es Schwellen, ab denen das große System entsteht.

  Knuths Zufallsgraphen sind allerdings eher topologisch als
  geometrisch definiert - es gibt also keinen bestimmten Abstand
  zwischen zwei Punkten. Bei Knuth kann jeder Punkt mit jedem
  anderen verbunden werden, bei Perkolation nur benachbarte Punkte.

[toc] | [prev] | [next] | [standalone]

#143990

Joachim Pimiskern <JoachimPimiskern@web.de> schrieb oder zitierte:
>Am 08.07.2026 um 13:02 schrieb Stefan Ram:
>>Nach der Schwelle   Sobald die Grenze überschritten wird,
>>verschmelzen diese Cluster schlagartig zu einer einzigen
>>Riesenkomponente" (Giant Component), die den Großteil
>>des Netzwerks verbindet.
>Das erinnert mich an den Begriff Perkolation.

  Und nun hat Claude die Kozma-Nitzan-Vermutung bewiesen, wodurch
  die "Vermutung über die sterbende Perkolation" (theta(p_c)=0)
  für alle Dimensionen bewiesen ist. Ein Mensch würde dafür sehr 
  wahrscheinlich die Fields-Medaille erhalten.

  Wikipedia: "Dying percolation conjecture"

[toc] | [prev] | [standalone]

Back to top | Article view | de.sci.mathematik

csiph-web