Komponenten, groß und klein, sind wie sie sein sollten I: superkritische Perkolation auf regulären Graphen mit wachsendem Grad

Grundinformationen

• Paper-ID: 2408.04597
• Titel: Components, large and small, are as they should be I: supercritical percolation on regular graphs of growing degree
• Autoren: Sahar Diskin, Michael Krivelevich (Universität Tel Aviv)
• Klassifizierung: math.CO (Kombinatorik), math.PR (Wahrscheinlichkeitstheorie)
• Veröffentlichungszeitpunkt: Eingereicht August 2024, überarbeitete Fassung November 2025
• Paper-Link: https://arxiv.org/abs/2408.04597

Zusammenfassung

Diese Arbeit liefert hinreichende Bedingungen für d-reguläre Graphen G mit wachsendem Grad, um sicherzustellen, dass ihre zufälligen Subgraphen Gₚ bei p·d≈1 einen Phasenübergang ähnlich dem klassischen Erdős-Rényi-Zufallsgraph G(n,p) aufweisen. Wenn G ein d-regulärer Graph auf n Knoten ist (d=ω(1)) und p=(1+ε)/d, dann enthält Gₚ unter milden Kantenexpansionsbedingungen und guter Kontrolle der Expansion kleiner Mengen typischerweise eine eindeutige Riesenkomponente der Ordnung y(ε)n (wobei y(ε) die Überlebenswahrscheinlichkeit eines Galton-Watson-Baums mit Parameter Po(1+ε) ist), während alle anderen Zusammenhangskomponenten die Ordnung O(log n/ε²) haben. Die Autoren zeigen auch, dass dieses Ergebnis scharf ist: Wenn die Kontrolle der Expansion kleiner Mengen schwächer ist, existieren d-reguläre Graphen, bei denen die zweitgrößte Zusammenhangskomponente die Ordnung Ω(d log(n/d))=ω(log n) hat.

Forschungshintergrund und Motivation

Forschungsfrage

Diese Arbeit untersucht das Problem der superkritischen Perkolation auf regulären Graphen: Gegeben ein Gastgraph G und eine Wahrscheinlichkeit p∈0,1, erhält man den Perkolations-Zufallsgraph Gₚ durch unabhängiges Beibehalten jeder Kante von G mit Wahrscheinlichkeit p. Die zentrale Frage ist: Welche regulären Graphen G zeigen das Erdős-Rényi-Komponentenphänomen (ERCP), d.h., in der superkritischen Phase p=(1+ε)/d eine eindeutige Riesenkomponente mit allen anderen Komponenten von logarithmischer Ordnung?

Bedeutung des Problems

1. Einheitliches Verständnis von Phasenübergängen: Erdős und Rényi bewiesen 1960 den Phasenübergang in klassischen Zufallsgraphen G(n,p) bei p·n≈1. Dieses Phänomen wurde unabhängig für verschiedene spezielle Graphen nachgewiesen (vollständige Graphen, Hyperwürfel, pseudozufällige Graphen usw.), aber mit unterschiedlichen Beweismethoden. Diese Arbeit zielt auf einen einheitlichen Rahmen ab.
2. Charakterisierung der Universalitätsklasse: Die Identifikation, welche Graphenstruktureigenschaften das Auftreten von ERCP bestimmen, hilft, die Universalität in der Perkolationstheorie zu verstehen.
3. Theoretische Vollständigkeit: Da bekannt ist, dass bestimmte Graphen (wie disjunkte Vereinigungen von Cliquen) ERCP nicht aufweisen, müssen die genauen Grenzbedingungen charakterisiert werden.

Beschränkungen bestehender Methoden

• Abhängigkeit von speziellen Strukturen: Der Beweis für Hyperwürfel beruht auf seiner Produktstruktur und Harper-Isoperimetrie; der Beweis für pseudozufällige Graphen beruht auf Expansions-Mischungs-Lemmata
• Verstreute Beweistechniken: Verschiedene Graphklassen erfordern völlig unterschiedliche Beweistechniken, es fehlt eine einheitliche Perspektive
• Unklare Bedingungen: Für allgemeine reguläre Graphen ist unklar, welche Expansionseigenschaften ERCP garantieren
• Unbekannte Schärfe: Ob bestehende hinreichende Bedingungen notwendig sind, ist ungeklärt

Forschungsmotivation

Die Autoren zielen darauf ab, ERCP durch reine Expansionseigenschaften (statt spezieller Strukturen) zu charakterisieren, einen einheitlichen Beweisrahmen bereitzustellen und durch Konstruktion von Gegenbeispielen die Schärfe der Bedingungen zu zeigen.

Kernbeiträge

1. Einheitlicher Rahmen hinreichender Bedingungen: Präsentation eines auf Expansionseigenschaften basierenden Rahmens (Theorem 1), der Fälle mit d≥log^α n abdeckt und einheitlich ERCP für vollständige Graphen, Hyperwürfel, d-reguläre Expansionsgraphen, zufällige d-reguläre Graphen und weitere Graphklassen beweist.
2. Drei Haupttheoreme:
   • Theorem 1 (d≥log^α n): Erfordert globale milde Kantenexpansion (P1), Knotenexpansion kleiner Mengen (P2), nahezu optimale Kantenexpansion kleiner Mengen (P3)
   • Theorem 3 (d≥10log n/ε): Entfernt (P2), benötigt nur (P1) und verstärkte (P2')
   • Theorem 4 (d=ω(1)): Entfernt (P2) und Gradschranke, benötigt aber verstärkte (P3) für größere Mengen
3. Schärfeergebnisse (Theorem 2): Konstruktion von Gegenbeispielen, die zeigen, dass die Bedingung (P3) für kleine Mengen im Sinne konstanter Faktoren scharf ist – wenn nur für Mengen der Größe ≤εd log(n/d)/(100c₁) nahezu optimale Kantenexpansion gefordert wird, existieren Graphen, bei denen die zweitgrößte Komponente Ω(d log(n/d)) ist.
4. Neue technische Innovationen:
   • Beweis, dass große Komponenten "überall dicht" sind
   • Doppelbelichtungs-/Sprinkle-Technik
   • Gap-Lemma für Komponentengrößen
5. Einheitliches Beweisparadigma: Bereitstellung eines reinen Expansionsbeweises, der nicht auf speziellen Strukturen (wie Produktstruktur oder Pseudozufälligkeit) beruht.

Methodische Details

Aufgabendefinition

Eingabe: d-regulärer Graph G=(V,E), n=|V|, Grad d=ω(1), Perkolationswahrscheinlichkeit p=(1+ε)/d (ε>0 kleine Konstante)
Ausgabe: Beweis, dass Gₚ mit hoher Wahrscheinlichkeit (whp) folgende Eigenschaften hat:

• Existiert eindeutige Riesenkomponente L₁ mit |L₁|=(1+o(1))y(ε)n
• Alle anderen Zusammenhangskomponenten haben Ordnung O(log n/ε²)

wobei y(ε)∈(0,1) die eindeutige Lösung der Gleichung y=1-exp{-(1+ε)y} ist, d.h. die Überlebenswahrscheinlichkeit eines Verzweigungsprozesses mit Parameter Po(1+ε).

Kernhypothesenbedingungen

Theorem 1 erfordert, dass G erfüllt:

(P1) Globale Kantenexpansion: Für alle U⊆V mit |U|≤n/2 gilt e(U,U^C)≥c₁|U| (c₁>0 Konstante)

(P2) Knotenexpansion kleiner Mengen: Für alle U⊆V mit |U|≤c₂log n gilt |N(U)|≥c₃d|U| (c₂,c₃>0 Konstanten)

(P3) Nahezu optimale Kantenexpansion kleiner Mengen: Für alle U⊆V mit |U|≤Cd log n gilt e(U,U^C)≥(1-ε³)d|U| (C hinreichend große Konstante)

Beweisarchitektur

Gesamtstrategie

Verwendung der Doppelbelichtungstechnik: Setze p₂=ε³/d und wähle p₁ so, dass (1-p₁)(1-p₂)=1-p, dann hat Gₚ die gleiche Verteilung wie Gₚ₁∪Gₚ₂. Der Beweis besteht aus vier Hauptschritten:

Schritt 1: Große Komponenten sind überall dicht (Abschnitt 3.1)

• Definition "große Komponente": VL(H)={v: |C_H(v)|≥7log n/ε²}
• Ziel: Beweis, dass whp jeder Knoten v in Distanz 1+log_d log n Ω(d log n) Knoten aus VL(Gₚ) hat

Schritt 2: Gap-Lemma für Komponentengrößen (Lemma 3.4)

• Beweis, dass whp keine Komponente der Ordnung in 7log n/ε², Cd log n existiert
• Erfordert feine Zählungen und Wahrscheinlichkeitsschätzungen

Schritt 3: Große Komponenten verschmelzen (Abschnitt 3.2, Lemma 3.5)

• Beweis, dass whp alle großen Komponenten in Gₚ₁ nach Sprinkle mit Gₚ₂ zu einer Komponente verschmelzen
• Schlüssel: Konstruktion ausreichend vieler knotendisjunkter Pfade

Schritt 4: Volumenkonzentration (Abschnitt 3.3, Lemma 3.8)

• Beweis, dass die Gesamtzahl der Knoten in der großen Komponente sich um y(ε)n konzentriert

Technische Details

Lemma 3.1: Komponentenverhalten für feste Mengen

Für |S|=c'd log n (c'=c₂c₃^(1+1/α)) beweise:

• (a) Es existiert kein U⊆S, so dass ∪{u∈U}C{Gₚ}(u) Ordnung in c'd log n/ε³, 2c'd log n/ε³ hat
• (b) Es existiert keine große Teilmenge U⊆S (|U|≥(1-ε²)c'd log n), so dass ∪{u∈U}C{Gₚ}(u) Ordnung ≤Cd log n hat

Beweistechniken:

• Verwendung von Waldzählung (Lemma 2.3): Höchstens (ed)^(k-1) Bäume auf k Knoten
• Nutzung von (P3): Grenze hat mindestens (1-ε³)kd Kanten, die nicht in Gₚ sein dürfen
• Wahrscheinlichkeitsschätzung: (edp)^(k-1)(1-p)^((1-ε³)kd) ≤ exp{-ε²k/4}

Lemma 3.3: Überall-Dichte-Eigenschaft

Beweis, dass whp jeder v∈V in Distanz ≤1+log_d log n mindestens ε²c'd log n Knoten aus VL(Gₚ) hat.

Beweisweg:

1. Nach (P2): |B_G(v, log_d log n)|≥c₂c₃^(log_d log n) log n≥c₂c₃^(1/α) log n
2. Erneute Anwendung von (P2): |B_G(v, 1+log_d log n)|≥c₃d·c₂c₃^(1/α) log n=c'd log n
3. Für Sv⊆B_G(v, 1+log_d log n) mit |Sv|=c'd log n folgt aus Corollary 3.2: |Sv∩VL(Gₚ)|≥ε²c'd log n
4. Union-Bound über alle v vervollständigt den Beweis

Lemma 3.5: Verschmelzung großer Komponenten

Setze W=VL(Gₚ₁). Für jede Partition W=A⊔B, die Komponenten von W respektiert, muss ein Pfad von A zu B in Gₚ₂ gefunden werden.

Konstruktionsprozess (angenommen |A|≤|B|):

1. Definiere A₀=A, B₀=B, konstruiere rekursiv Aᵢ, Bᵢ (i=1,...,r, r=1+log_d log n):
   • Aᵢ enthält Knoten mit ≥ε²c'd/(5r) Nachbarn zu Aᵢ₋₁
   • Bᵢ ähnlich definiert
2. Claim 3.6: V=A'⊔B', wobei A'=∪Aᵢ, B'=∪Bᵢ
3. Exponiere Kanten von A' zu B' in Gₚ₂, nach Lemma 2.4 existiert Matching M mit |M|≥ε⁶c₁|A|/d
4. Erweitere rekursiv die Endpunkte von M durch Pfade in Gₚ₂ zu A₀=A
5. Ähnlich von B' zu B, verbinde schließlich A und B

Wahrscheinlichkeitsschätzung:

• Fehlerwahrscheinlichkeit pro Schritt ≤exp{-ε⁸c'|Mᵢ,A'|/(5r)}
• Finale Pfadzahl ≥(ε⁸c'c₁/(5r))^(r+1)|A|/d
• Partitionszahl ≤n^(|A|/(Cd log n))
• Union-Bound: ≤2n·exp{-(ε⁸c'c₁/(7r))^(2r+1)C log n}=o(1)

Lemma 3.4: Gap-Lemma

Beweis, dass whp keine zusammenhängende Menge K mit |K|∈7log n/ε², Cd log n und E_{Gₚ₁}(K,K^C)=∅ existiert.

Schlüsselschätzung:

• Baum T der Ordnung k: Höchstens n(ed)^(k-1) Möglichkeiten
• Nach (P3): e(V(T), V\V(T))≥(1-ε³)kd
• Palle Kanten in Gₚ und Grenze ohne Kanten in Gₚ₁≤n(edp)^(k-1)exp{-p₁(1-ε³)dk}
• ≤n exp{k(1+log(1+ε)-(1+ε-3ε³))}≤n exp{-ε²k/3}=o(1/n)

Lemma 3.8: Volumenkonzentration

Setze W als Menge der Knoten in Komponenten von Gₚ mit Ordnung ≥14log n/ε².

Erwartungswertberechnung:

• Fixiere v, erkunde durch BFS, dominiert durch Bin(d,p)-Verzweigungsprozess
• P|C_{Gₚ}(v)|≥14log n/ε²≤(1+o(1))y(ε) (Obergrenze)
• Modifiziere BFS, stoppe bei √d Schritten, dominiert durch Bin(d-√d,p)
• P|C_{Gₚ}(v)|≥√d≥(1-o(1))y(ε) (Untergrenze)
• Nach Lemma 3.7: EW=(1+o(1))y(ε)n

Konzentration:

• Kantenexpositions-Martingal, jede Kante ändert |W| um höchstens 28log n/ε²
• Nach Azuma-Hoeffding (Lemma 2.2): P||W|-EW|≥n^(2/3)≤2exp{-n^(4/3)/(O(ndp·log²n/ε⁴))}=o(1)

Technische Innovationspunkte

1. Neuer Beweis der Überall-Dichte: Unabhängig von Produktstruktur, rein durch Ballwachstum und Knotenexpansion etabliert
2. Rekursive Strategie für Pfadkonstruktion: Bei Sprinkle-Wahrscheinlichkeit p₂=ε³/d könnte die Wahrscheinlichkeit für Pfade der Länge r=O(log_d log n) sehr klein sein (p₂^r), gelöst durch rekursive Matching und Mengen-Konstruktion Aᵢ
3. Präzise Konstanten im Gap-Lemma: Das Gap von 7log n/ε² zu Cd log n ist für nachfolgende Argumente entscheidend, die Konstantenwahl ist eng mit p₂=ε³/d verbunden (bezogen auf Taylor-Entwicklung von log(1+x))
4. Schärfekonstruktion (Theorem 2): Durch c'₁-reguläre Graphen H (erfüllt globale Expansion) plus Graphen innerhalb Farbklassen konstruiert, so dass Farbklassen in Gₚ isoliert sind

Experimentelle Einrichtung

Diese Arbeit ist eine reine theoretische mathematische Arbeit ohne Computerexperimente. Alle Ergebnisse sind strenge mathematische Beweise.

Anwendungsbeispiele (als "Verifikation")

Die Arbeit zeigt, wie Theorem 1 und seine Varianten bekannte Ergebnisse wiederherstellen:

1. Vollständiger Graph Kₙ: Theorem 3 stellt das klassische Erdős-Rényi-Ergebnis wieder her
2. (n,d,λ)-Pseudozufallsgraphen (λ=o(d)): Expansions-Mischungs-Lemma verifiziert (P3), Theorem 3/4 anwendbar
3. Zufällige d-reguläre Graphen: Whp sind (n,d,Ω(√d))-Graphen, erfüllen alle Bedingungen
4. Hyperwürfel Qd: Harper-Isoperimetrie gibt e(U,U^C)≥|U|(d-log₂|U|), erfüllt (P1) und (P3); kleine Mengen-Knotenexpansion folgt aus Harper-Ergebnis
5. Hochdimensionale Produktgraphen: Erfüllen Bedingungen durch Harper-ähnliche Ungleichungen
6. Duplicube: Erfüllt Harper-ähnliche Ungleichungen, beantwortet Benjamini-Zhukovskii-Frage

Experimentelle Ergebnisse

Zusammenfassung der Hauptergebnisse

Theorem 1 (Polylogarithmischer Grad): d≥log^α n impliziert (P1)+(P2)+(P3) ⇒ ERCP

Theorem 3 (Hoher Grad): d≥10log n/ε impliziert (P1)+(P2') ⇒ ERCP, wobei (P2') für |U|≤min{Cd log n, ε⁵n} fordert e(U,U^C)≥(1-ε³)d|U|

Theorem 4 (Niedriger Grad): d=ω(1) impliziert (P1)+starke (P3) (|U|≤(d log n)^(5log log n)) ⇒ ERCP

Theorem 2 (Schärfe): Es existiert d-regulärer Graph G mit:

• (P1) erfüllt
• Für |U|≤log(n/d)/(40c₁): |N(U)|≥d|U|
• Für |U|≤ε³d log(n/d)/(100c₁): e(U,U^C)≥(1-ε³)d|U|
• Aber whp zweite Komponente ≥εd log(n/d)/(30c₁)=ω(log n)

Notwendigkeitsanalyse der Bedingungen

• (P1)-Notwendigkeit: 17 zeigt, dass zu schwache globale Expansion zu o(n) Riesenkomponente führt
• (P3)-Schärfe: Theorem 2 beweist Schärfe im Sinne konstanter Faktoren
• (P2)-Notwendigkeit: Offenes Problem (Problem 6.1), aber Theorem 3 und 4 zeigen, dass es unter bestimmten Umständen entfernt werden kann

Vergleich mit bestehenden Ergebnissen

Verwandte Arbeiten

Historische Entwicklung

1. Erdős-Rényi (1960): Etablierung der Phasenübergängstheorie für G(n,p)
2. Broadbent-Hammersley (1957): Einführung des Perkolationsmodells
3. Ajtai-Komlós-Szemerédi (1982): Beweis von ERCP für Hyperwürfel, erste Verwendung der "Überall-Dichte"-Strategie
4. Bollobás-Kohayakawa-Łuczak (1992): Alternativer Beweis für Hyperwürfel

Konstanter Grad

• Alon-Benjamini-Stacey (2004): Hochumfang-Expansionsgraphen haben Riesenkomponente
• Krivelevich-Lubetzky-Sudakov (2020): Riesenkomponente der Ordnung y(ε)n, aber zweite kann |V|^a (beliebiges a<1) erreichen
• Diskin-Krivelevich (2025, 18): Schwesterarbeit dieser Arbeit, behandelt konstanten Grad

Gradfolgen und Zufälligkeit

• Van der Hofstad (2023, 32): Universelle Grenzen für Riesenkomponente bei gegebener Gradfolge
• Lichev-Mitsche-Perarnau (2024): Schwellenwertcharakterisierung für Gradfolgen-Zufallsgraphen
• Alimohammadi-Borgs-Saberi (2023): Große Mengen-Expansion bestimmt lokale Struktur und Riesenkomponente

Positionierung dieser Arbeit

Diese Arbeit ist die erste, die einheitliche notwendige und hinreichende Bedingungen basierend auf reinen Expansionseigenschaften für reguläre Graphen mit wachsendem Grad bereitstellt und die Schärfe der Bedingungen beweist.

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

1. Für d-reguläre Graphen mit wachsendem Grad ist milde globale Kantenexpansion zusammen mit guter Expansionskontrolle für kleine Mengen (Größe O(d log n)) ausreichend für ERCP
2. Die Bedingung für kleine Mengen-Expansion ist im Sinne konstanter Faktoren scharf
3. Ein einheitlicher Beweisrahmen wird bereitgestellt, unabhängig von speziellen Strukturen (Produkt, Pseudozufälligkeit usw.)

Beschränkungen

1. Notwendigkeit von (P2) ungeklärt: Problem 6.1 fragt, ob Graphen existieren, die (P1) und (P3) erfüllen aber ERCP nicht zeigen?
2. Konstantenabhängigkeit: Konstanten in Theoremen hängen von ε, c₁, c₂, c₃, α ab, genaue Abhängigkeitsbeziehungen nicht vollständig optimiert
3. Quantitative Schärfe: Theorem 2 gibt qualitative Schärfe, aber präzise Konstanten-Matching hat Verbesserungspotential
4. Gradbereich: Fall d=ω(1) aber d=o(log n) benötigt starke Annahmen in Theorem 4

Zukünftige Richtungen

1. Problem 6.1: Charakterisierung der Notwendigkeit von (P2)
2. Quantitatives Gleichgewicht zwischen globaler und lokaler Expansion: Arbeit zeigt, dass stärkere (P1) schwächere (P3) erlaubt, präzise Charakterisierung dieses Gleichgewichts
3. Weitere Graphklassen: Können Permutaeder 13 mit ähnlichem Rahmen behandelt werden?
4. Algorithmische Anwendungen: Können Expansionsbedingungen für effizientes Sampling oder Approximationsalgorithmen verwendet werden?
5. Verallgemeinerung auf nicht-reguläre Graphen: 13,15,30 zeigen, dass unregelmäßige Graphen möglicherweise ERCP nicht zeigen, aber können präzisere Bedingungen gegeben werden?

Tiefenanalyse

Stärken

1. Theoretische Tiefe:
   • Bereitstellung eines einheitlichen mathematischen Rahmens, vermeidung von Fallanalysen
   • Schärfeergebnisse (Theorem 2) zeigen, dass Bedingungen nahezu optimal sind
   • Technische Innovationen (Überall-Dichte, rekursive Pfadkonstruktion) haben unabhängigen Wert
2. Beweistechniken:
   • Elegante Anwendung der Doppelbelichtungstechnik (Wahl p₂=ε³/d bezogen auf Taylor-Entwicklung)
   • Präzise Konstantenkontrolle im Gap-Lemma
   • Sorgfältige Wahrscheinlichkeitsschätzungen (z.B. Waldzählung in Lemma 3.1)
3. Breite Anwendbarkeit:
   • Wiederherstellung mehrerer klassischer Ergebnisse (vollständige Graphen, Hyperwürfel, pseudozufällige Graphen)
   • Lösung offener Probleme (ERCP für Duplicube)
   • Explizite Bedingungen für zufällige d-reguläre Graphen
4. Schreibklarheit:
   • Klare Struktur: Hintergrund→Hauptergebnisse→Beweis→Schärfe→Anwendungen
   • Explizite technische Roadmap: Vierschritt-Beweisstrategien leicht verständlich
   • Vollständiges Symbolsystem

Schwächen

1. Bedingungskomplexität:
   • Wechselwirkung der drei Eigenschaften (P1)(P2)(P3) nicht intuitiv genug
   • Abhängigkeitsbeziehungen zwischen Konstanten c₁, c₂, c₃, C nicht explizit gegeben
   • Praktische Verifikation, ob Graph Bedingungen erfüllt, kann schwierig sein
2. Offene Probleme:
   • Notwendigkeit von (P2) ungeklärt, theoretisches Bild unvollständig
   • Konstruktion in Theorem 2 beweist Schärfe, aber Konstanten-Matching nicht präzise
3. Technische Beschränkungen:
   • Für d=ω(1) aber d=o(log n) benötigt Theorem 4 starke Annahmen (Mengengröße bis (d log n)^(5log log n))
   • Beweistechniken stark abhängig von Regularitätsannahme, Verallgemeinerung auf nicht-reguläre Graphen schwierig
4. Anwendungsleitfaden:
   • Wie kann man für gegebenen Graph effizient verifizieren, ob (P2)(P3) erfüllt sind?
   • Fehlende algorithmische oder rechnerische Diskussion

Einfluss

1. Beitrag zum Gebiet:
   • Neue einheitliche Perspektive für Perkolationstheorie
   • Könnte Forschung zu anderen Zufallsgraph-Modellen inspirieren
   • Schwesterarbeit 18 erweitert auf konstanten Grad, bildet vollständige Theorie
2. Praktischer Wert:
   • Theoretische Grundlage für Netzwerk-Robustheit-Analyse
   • Kann für Design von Netzwerk-Topologien mit guten Perkolationseigenschaften verwendet werden
   • Expansionseigenschaften haben breite Anwendungen in Informatik
3. Reproduzierbarkeit:
   • Rein theoretischer Beweis, vollständig reproduzierbar
   • Beweistechniken detailliert, Schlüssellemmata vollständig bewiesen
   • Konstruktion in Theorem 2 praktisch implementierbar

Anwendungsszenarien

1. Theoretische Forschung:
   • Zufallsgraph-Theorie
   • Perkolationstheorie
   • Graphexpansions-Eigenschaften
   • Universalitätsklassen von Phasenübergängen
2. Netzwissenschaft:
   • Netzwerk-Robustheit-Analyse (Knoten-/Kantenausfälle)
   • Epidemiologische Ausbreitungsmodelle (Perkolation entspricht Ausbreitung)
   • Konnektivitätsanalyse sozialer Netzwerke
3. Kombinatorische Optimierung:
   • Graphpartitionierungsprobleme
   • Expansionsgraph-Konstruktion
   • Zufallsalgorithmus-Design

Literaturverzeichnis (Schlüsselliteratur)

1. 20 Erdős-Rényi (1960): Grundlegende Arbeit zu Phasenübergängen in Zufallsgraphen
2. 1 Ajtai-Komlós-Szemerédi (1982): Perkolation auf Hyperwürfeln, erste Verwendung von "Überall-Dichte"
3. 22 Frieze-Krivelevich-Martin (2004): ERCP für pseudozufällige Graphen
4. 29 Krivelevich-Lubetzky-Sudakov (2020): Universelle Grenzen für Riesenkomponente
5. 32 Van der Hofstad (2023): Universelle Grenzen für Riesenkomponente
6. 17 Diskin et al. (2024): Frühere Arbeit der Autoren zu Isoperimetrie und Perkolation
7. 18 Diskin-Krivelevich (2025): Schwesterarbeit (konstanter Grad)

Gesamtbewertung: Dies ist eine hochwertige theoretische mathematische Arbeit, die einen tiefgreifenden einheitlichen Rahmen für die Perkolationstheorie bereitstellt. Technisch rigoros und innovativ, mit breiter Anwendbarkeit und vollständiger Schärfeanalyse. Der Hauptbedauern ist die ungeklärte Notwendigkeit von (P2), was aber auch wertvollen Raum für zukünftige Forschung schafft. Diese Arbeit hat bedeutenden Einfluss auf Kombinatorik und Wahrscheinlichkeitstheorie mit potentiellen Verbindungen zur Netzwissenschaft.