\documentclass{article} \usepackage[utf8]{inputenc} \usepackage[ngerman]{babel} \usepackage[a4paper, margin=1.5cm]{geometry} \usepackage{amsthm} \usepackage{amssymb} \usepackage{amsmath} \usepackage{bbm} \usepackage{enumitem} \usepackage{titling} \usepackage{mathtools} \usepackage[sc]{mathpazo} \usepackage[euler-digits,small]{eulervm} \setlength{\parindent}{0mm} \renewcommand{\baselinestretch}{1.3} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\E}{\mathbb{E}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\1}{\mathbbm{1}} \renewcommand{\P}{\mathbb{P}} \newtheoremstyle{custom} {}% Space above {}% Space below {}% Body font {}% Indent amount {\bfseries} % Thm head font {.}% Punctuation after thm head {\newline}% Space after thm head {}% Thm head spec \theoremstyle{custom} \newtheorem*{theorem}{Theorem} \newtheorem*{definition}{Definition} \newtheorem*{lemma}{Lemma} \newtheorem*{remark}{Beispiel} \renewcommand\qedsymbol{$\blacksquare$} \newenvironment{claim}[1]{\par\noindent\underline{Behauptung:}\space#1}{} \newenvironment{claimproof}[1]{\par\noindent\underline{Beweis:}\space#1}{\hfill $\square$} \pagestyle{empty} \title{Über die Anzahl unendlicher Cluster} \author{Adrian Kummerländer} \date{20. November 2017} \begin{document} \noindent\parbox{\linewidth}{% \parbox{.6\linewidth}{\fontsize{18}{22}\selectfont\thetitle}\hfill% \parbox{.4\linewidth}{\fontsize{12}{14}\selectfont\raggedleft\thedate\\\theauthor% }} \vspace*{0.5cm} \begin{definition}[Notation von teilweise geänderten Konfigurationen] Seien $X : \{0,1\}^{E(G)} \to \R \cup \{-\infty,+\infty\}$ eine Zufallsvariable, $\omega \in \{0,1\}^{E(G)}, \eta \in \{0,1\}^{E(G)}$ Konfigurationsvektoren und $E \subset E(G)$ eine Teilmenge der Kanten von $G$. \vspace*{1mm} Wir definieren die Konfiguration $\omega_{\eta,E}$, in welcher die Zustände aller Kanten $E$ auf die entsprechende Werte des Konfigurationsvektors $\eta$ geändert wurden: $\omega_{\eta,E}(e) := \1_{\{e \in E\}}\eta(e) + \mathbbm{1}_{\{e \notin E\}}\omega(e)$. \vspace*{1mm} Für die besonderen Fälle $\eta \equiv 1$ und $\eta \equiv 0$ schreiben wir: $\omega_{1,E}(e) := \1_{\{e \in E\}} + \1_{\{e \notin E\}} \omega(e)$ bzw. $\omega_{0,E}(e) := \1_{\{e \notin E\}} \omega(e)$. \vspace*{1mm} $X_{1,E}(\omega) := X(\omega_{1,E})$ bzw. $X_{0,E}(\omega) := X(\omega_{0,E})$ ist der Wert der Zufallsvariable $X$ unter der geänderten Konfiguration. \end{definition} \begin{lemma}[Yadin 6.1, \emph{0-1-$\infty$-Gesetz}] Seien $G$ ein transitiver, unendlicher sowie zusammenhängender Graph und $N : \{0,1\}^{E(G)} \to \N_0 \cup \{\infty\}$ zähle die Anzahl unendlicher Cluster bei Perkolation auf $G$. Dann gilt $\forall p \in (0,1) \exists k \in \{0,1,\infty\} : \P_p[N=k] = 1$. \end{lemma} \begin{proof} Für $\forall k \in \{0,1,\dots,\infty\}$ ist das Ereignis $\{N=k\}$ translationsinvariant. Aus \emph{Yadin 2.2} folgt direkt: $\P_p[N=k] \in \{0,1\} \implies \exists! k_p \in \{0,1,\dots,\infty\} : \P_p[N=k_p]=1$ Sei nun $B \subset G$ ein endlicher Teilgraph von $G$ s.d. die Menge der Kanten $E(B)$ nicht leer ist. Wir definieren Ereignisse: \vspace*{-2mm} \begin{description} \itemsep-1mm \item[$C_B$:] Alle Kanten in $E(B)$ sind bei $p$-Perkolation auf $G$ geschlossen \item[$O_B$:] Alle Kanten in $E(B)$ sind bei $p$-Perkolation auf $G$ geöffnet \end{description} Da $B$ endlich ist, haben $C_B$ und $O_B$ für $p \in (0,1)$ eine positive Wahrscheinlichkeit. Wir definieren zwei Zufallsvariablen auf Grundlage der Anzahl $N$ unendlicher Cluster: \vspace*{-2mm} \begin{description} \itemsep-1mm \item[$N_C := N_{0,E(B)}$] Anzahl unendlicher Cluster in $G$, wenn alle Kanten in $E(B)$ geschlossen werden \item[$N_O := N_{1,E(B)}$] Anzahl unendlicher Cluster in $G$, wenn alle Kanten in $E(B)$ geöffnet werden \end{description} Wir erkennen an dieser Stelle die Verknüpfung zwischen der aus Perkolation hervorgehenden Graphkonfiguration $\omega$, den in $B$ geschlossenen bzw. geöffneten Konfigurationen $\omega_{0,E(B)}$ und $\omega_{1,E(B)}$ sowie den Ereignissen $C_B$ und $O_B$: \vspace*{-4mm} $$\omega_{0,E(B)} =: \omega_C = \omega \iff \omega \in C_B \text{ und } \omega_{1,E(B)} =: \omega_O = \omega \iff \omega \in O_B$$ Darüber hinaus gilt $N_C, N_O \in \mathcal{T}_{E(B)}$ d.h. $N_C$ und $N_O$ sind unabhängig von $E(B)$. Mit $\P[C_B], \P[O_B] > 0$ und $k=k_p$ folgt nun: \vspace*{-4mm} \begin{align*} \P_p[N_C=k] &= \P_p[N_C = k | C_B] && N_C \text{ unabhängig von } E(B) \text{, insb. also von Ereignis } C_B \\ &= \P_p[N_C=N=k | C_B] && C_B \text{ ist Vorbedingung, d.h. Schließen von $E(B)$ ändert $N$ nicht} \\ &= \P_p[N=k | C_B] && \text{$N_C$ kann weggelassen werden} \\ &= 1 && \text{$\P_p[N=k_p]=1$ wie gezeigt, $N$ unabhängig $E(B)$} \end{align*} Analog für $N_O$: $\P_p[N_O=k] = \P_p[N_O=k|O_B] = \P_p[N_O=N=k|O_B] = \P_p[N=k|O_B] = 1$. Insgesamt folgt also $\P_p[N_C=N_O=k]=1$, d.h. die Anzahl unendlicher Cluster ist fast sicher von $E(B)$ unabhängig. Sei nun $N_B$ die Anzahl unendlicher Cluster welche $B$ schneiden. Öffnen wir alle Kanten in $E(B)$, so verbinden wir alle diese Cluster zu einem einzigen unendlichen Cluster. Schließen wir alle Kanten in $E(B)$, so trennen wir die unendlichen Cluster und erhöhen möglicherweise deren Anzahl durch Spaltung: \vspace*{-4mm} $$N_B \geq 2 \land N < \infty \implies N_O \leq N-1 \land N_C \geq N$$ Mit $\P_p[N_C=N_O=k_p]=1$ folgt $\forall p \in (0,1), k_p < \infty : \P_p[N_B \geq 2] \leq \P_p[N_O \leq N - 1] \leq \P_p[N_O \leq N_C - 1] = 0$. Wir fixieren nun einen Knoten $v \in V(G)$ und definieren $B(v,r) \subset G$ als die Kugel mit Radius $r > 0$ um $v$ entsprechend der Graph-Metrik $\text{dist}_G$. Sei $N_r$ die Anzahl unendlicher Cluster welche diese Kugel schneiden. Mit $k_p < \infty \implies \P_p[N_r \geq 2]=0$ und $N_r \nearrow N$ schließen wir $k_p \in \{0,1,\infty\}$. \end{proof} \begin{definition}[Äußerer Rand, Isoperimetrische Konstante] Sei $G$ ein zusammenhängender Graph und $S \subset G$ ein endlicher Teilgraph. Wir definieren den \emph{äußeren Rand} von $S$ als: $\partial S := \{ x \notin S | x \sim S \}$ Hierbei bezeichnet $x \sim S$ den Knoten $x$ als adjazent zu einem Knoten in $S$. Wir definieren die \emph{isoperimetrische Konstante}: \vspace*{-3mm} $$\Phi = \Phi(G) := \inf\left\{ \frac{|\partial S|}{|S|} \middle| S \subset G \text{ endlich, zusammenhängend}\right\} \in [0,1]$$ \end{definition} \begin{definition}[Amenable Graphen, Folner-Folgen] Ist die isoperimetrische Konstante eines Graphen $\Phi(G) = 0$, so nennen wir $G$ einen \emph{amenablen} Graphen. Eine Folge von endlichen zusammenhängenden Teilgraphen $(S_n)_{n\in\N}$ mit $\frac{|\partial S_n|}{|S_n|} \to 0$ für $n \to \infty$ wird \emph{Folner-Folge} genannt, die Teilgraphen heißen \emph{Folner-Teilgraphen}. \end{definition} \begin{remark}[$\Z^d$ ist amenabler Graph] Das Gitter $\Z^d$ ist ein amenabler Graph $G$ wenn $\Phi(\Z^d)=0$ gilt, d.h. wenn für einen endlichen zusammenhängenden Teilgraphen die Kardinalität des äußeren Randes ggü. der des Teilgraphen selbst zu vernachlässigen ist. \vspace*{2mm} Zum Beweis betrachten wir eine Folge $(S_{i,d})_{i \in \N}$ von $d$-dimensionalen Hyperwürfeln mit Seitenlänge $i \in \N$: \vspace*{-6mm} \begin{align*} V(S_{i,d}) &:= \{ (x_1,\dots,x_d) \in \Z^d | \forall j \in \{1,\dots,d\} : 0 \leq x_j < i \} \\ E(S_{i,d}) &:= \{ \{x,y\} \in E(\Z^d) | x, y \in V(S_{i,d}) \} \end{align*} \vspace*{-8mm} \vspace*{2mm} Sei hierbei $|\partial S_{i,d}| = 2 \cdot d \cdot i^{d-1}$ die Anzahl der äußeren Randknoten und $|S_{i,d}| = i^d$ die Anzahl der inneren Knoten. Offensichtlich gilt $\displaystyle\forall d \in \N : \lim_{i \to \infty} \frac{|\partial S_{i,d}|}{|S_{i,d}|} = \lim_{i \to \infty} \frac{2 \cdot d \cdot i^{d-1}}{i^d} = \lim_{i \to \infty} \frac{2 \cdot d}{i} = 0$. \vspace*{2mm} Wir bemerken, dass $(S_{i,d})_{i \in \N}$ eine \emph{Folner-Folge} ist. Amenable Graphen können also äquivalent als Graphen für die eine Folner-Folge existiert charakterisiert werden. \end{remark} \begin{definition}[$r$-Trifurkationspunkt] Seien $G$ ein unendlicher zusammenhängender Graph und $x \in V(G)$ ein Knoten. Dann bezeichnet $B(x,r)$ die Kugel mit Radius $r > 0$ um $x$ bzgl. der Graph-Metrik $\text{dist}_G$. Für Perkolation auf $G$ sei $N_r$ die Anzahl der $B(x,r)$ schneidenden unendlichen Cluster. Sei $M_r := (N_r)_{0,E(B(x,r))}$ die Anzahl dieser unendlichen Cluster, wenn alle Kanten in $B(x,r)$ geschlossen werden. Wir definieren $\Psi_r(x)$ als das Ereignis, dass $x$ ein \emph{$r$-Trifurkationspunkt} ist. Dies ist der Fall, wenn gelten: \vspace*{-2mm} \begin{enumerate}[label=(\alph*)] \itemsep0em \item $B(x,r)$ schneidet einen unendlichen Cluster, d.h. $N_r \geq 1$ \item Werden alle Kanten in $B(x,r)$ geschlossen, so ist die Anzahl der schneidenden unendlichen Cluster $M_r \geq 3$ \end{enumerate} \end{definition} \begin{lemma}[Yadin 6.9] Sei $G$ ein transitiver, unendlicher und zusammenhängender Graph. Sei $N$ die Anzahl unendlicher Cluster bei Perkolation auf $G$. Dann gilt $\forall p \in (0,1) \exists r > 0 : ( \P_p[N = \infty]=1 \implies \forall x \in V(G) : \P_p[\Psi_r(x)] > 0 )$ \vspace*{2mm} d.h. wenn bei $p$-Perkolation auf $G$ fast sicher unendlich viele Cluster existieren, dann gibt es auch einen Radius $r$, für den alle Knoten in $G$ mit positiver Wahrscheinlichkeit $r$-Trifurkationspunkte sind. \end{lemma} \begin{proof} Seien $N_r$ die Anzahl unendlicher Cluster welche die Kugel $B(x,r)$ um beliebiges $x \in V(G)$ schneiden und $M_r$ die Anzahl wenn alle Kanten in der Kugel geschlossen werden. Gilt nun $\P_p[N=\infty]=1$, so folgt mit $N_r \nearrow N$: $\exists r := r_p > 0 : \P_p[N_r \geq 3] \geq \frac{1}{2}$. Wir bemerken, dass beim Schließen der Kanten alle schneidenden unendlichen Cluster in neue, ebenfalls schneidende, aber nicht zwingend unendliche, Cluster zerfallen. Je mindestens einer der neuen Cluster muss aber unendlich sein, womit $\P_p[M_r \geq N_r] = 1$ folgt. Zusammenfassend: $$\P_p[\Psi_r(x)] = \P_p[M_r \geq 3, N_r \geq 1] \geq \P_p[N_r \geq 3] \geq \frac{1}{2} > 0$$ \end{proof} \newpage \begin{lemma}[Yadin 6.10] Sei $G$ ein unendlicher zusammenhängender Graph und $S \subset G$ ein endlicher zusammenhängender Teilgraph. Dann ist die Anzahl von $r$-Trifurkationspunkten in $S$ maximal $\Delta(G)^r|\partial S|$. Hierbei bezeichnet $\Delta(G)$ den maximalen Knotengrad in $G$. \end{lemma} \begin{proof} Sei für $S$ und $S^\prime := \bigcup_{s\in S} B(s,r)$ ein Hilfsgraph $\Psi$ wie folgt definiert: \vspace*{-6mm} \begin{align*} V(\Psi) &:= \{ x \in S | x \text{ ist } r\text{-Trifurkationspunkt } \} \cup \{x \in \partial S^\prime | x \text{ ist Teil eines unendlichen Cluster }\} \\ E(\Psi) &:= \{ \{x,y\} \in V(\Psi)^2 | \exists \text{offener Pfad } B(x,r) \leftrightarrow B(y,r) \text{ auf unendlichem Cluster, der durch kein } B(z,r) \text{ verläuft} \} \end{align*} $\Psi$ ist also ein Graph aller $r$-Trifurkationspunkte in $S$ zusammen mit genau den äußeren Randpunkten von $S^\prime$, die Teil eines unendlichen Clusters sind. Die Betrachtung von $\partial S^\prime$ anstatt $\partial S$ ist hierbei notwendig, um zu garantieren, dass alle Cluster, die Kugeln um Trifurkationspunkte in $S$ schneiden, auch den für $\Psi$ relevanten äußeren Rand schneiden und somit als Knoten in $\Psi$ repräsentiert sind. Wir bemerken, dass das Entfernen eines $r$-Trifurkationspunktes aus $\Psi$ diesen Graphen in mindestens drei Zusammenhangskomponenten aufspaltet. Insbesondere existieren für einen $r$-Trifurkationspunkt $x \in \Psi \cap S$ drei, $S^\prime \setminus B(x,r)$ schneidende, unendliche Cluster, die außerhalb von $B(x,r)$ nicht verbunden sein können. d.h. $\Psi$ beinhaltet mindestens drei Knoten aus $\partial S^\prime$, die in $\Psi$ nur über Trifurkationspunkte verbunden sein können. \vspace*{2mm} \begin{claim} Seien $\Psi$ ein Graph und $V \subset V(\Psi)$ eine Knotenmenge s.d. $\forall v \in V$ der auf $\Psi \setminus \{v\}$ induzierte Graph mindestens drei Zusammenhangskomponenten hat. Dann gilt $2|V| + 2 \leq |\Psi|$. \end{claim} \begin{claimproof} Wir beweisen diese Zwischenbehauptung mit Induktion auf $|V|$. Für $|V|=1$ ist die Behauptung klar, da $|\Psi \setminus \{v\}| \geq 3$ für $V=\{v\}$. Für $|V|=n+1$ seien $v \in V$ und $C_1, \dots, C_k$ mit $k \geq 3$ die Zusammenhangskomponenten von $\Psi \setminus \{v\}$. Seien $w_1, w_2$ Hilfsknoten und $\Psi_i$ für $i \in \{1,2\}$ wie folgt definierte Graphen: \vspace*{-6mm} \begin{align*} V(\Psi_i) &:= \{w_i\} \cup V(C_i) \\ E(\Psi_i) &:= \{ \{w_i,c\} \} \cup E(C_i) \text{ wobei } c \in V(C_i) \text{ der eindeutige Knoten mit } c \sim v \text{ ist} \end{align*} Weiter sei $w_3$ ein Hilfsknoten und $\Psi_3$ wie folgt definiert: \vspace*{-6mm} \begin{align*} V(\Psi_3) &:= \{w_3\} \cup V(C_3) \cup \dots \cup V(C_k) \\ E(\Psi_3) &:= \{ \{w_3,c_i\} | c_i \in V(C_i) \text{ mit } c_i \sim v \text{ für } i \in \{3,\dots,k\} \} \cup E(C_3) \cup \dots \cup E(C_k) \end{align*} Sei $V_j := V \cap C_j$. Dann gilt $|V_j| \leq n$ wegen $v \notin V_j$ und $\forall v \in V_j$ habe $\Psi_j \setminus \{v\}$ mindestens drei Komponenten. Wir können also die Induktionsannahme, dass für $|V| \leq n$ die Abschätzung $2|V|+2 \leq |\Psi|$ gilt, anwenden. Konkret gilt für $j \in \{1,2,3\} : 2|V_j|+2 \leq |\Psi_j|$. Dies gilt insbesondere auch für $V_j = \emptyset$ da $|\Psi_j| \geq 2$. Zusammenfassend: \vspace*{-6mm} \begin{align*} 2|V| &= 2 \cdot ( 1 + |V_1| + |V_2| + |V_3| ) && C_i \text{ sind paarweise disjunkt und } v \notin V_j\\ &\leq 2 + |\Psi_1| + |\Psi_2| + |\Psi_3| - 6 && \text{schätze ab mit } 2|V_j| \leq |\Psi_j| - 2 \\ &= ( |\Psi \setminus \{v\}| + 3 ) - 4 && |\Psi_1|+|\Psi_2|+|\Psi_3|=|\Psi \setminus \{v\}|+|\{w_1,w_2,w_3\}| \\ &= |\Psi| - 1 + 3 - 4 && |\Psi\setminus\{v\}| = |\Psi|-1 \\ &= |\Psi| - 2 \end{align*} \end{claimproof} \vspace*{2mm} Mithilfe dieser Zwischenbehauptung erhalten wir für die Anzahl $T$ der $r$-Trifurkationspunkte in $S$ die Abschätzung: $2T \leq |\Psi|-2 = T+(|\Psi|-T)-2$. Da jeder Knoten in $\Psi$, der kein $r$-Trifurkationspunkt ist, ein äußerer Randpunkt sein muss (also $|\Psi| - T \leq |\partial S^\prime|$ gilt), können wir schließen: $2T \leq T + |\partial S^\prime| - 2$. Insbesondere ist also $T < |\partial S^\prime|$. \vspace*{2mm} Zur Vervollständigung der Behauptung fehlt nun nur noch die Abschätzung $|\partial S'| \leq \Delta(G)^r|\partial S|$: Jeder Knoten in $\partial S^\prime$ hat Abstand $r$ von einem Knoten in $\partial S$. Daraus folgt zusammen mit der bisherigen Abschätzung: $$T < |\partial S^\prime| \leq \sum_{x \in \partial S} |\partial B(x,r-1)| \leq \sum_{x \in \partial S} \Delta(G)^r = \Delta(G)^r \cdot |\partial S|$$ \end{proof} \begin{theorem}[Yadin 6.11, Burton-Keane] Sei $G$ ein transitiver unendlicher, zusammenhängender und amenabler Graph. Dann gilt $\forall p \in (0,1) \exists k_p \in \{0,1\} : \P_p[N=k_p]=1.$ Es existiert also fast sicher entweder kein oder genau ein unendlicher Cluster. \end{theorem} \begin{proof} Seien $v \in V(G)$ ein beliebiger aber fester Knoten, $(S_n)_{n \in \N}$ eine Folner-Folge, $r := r_p > 0$ s.d. mit Annahme von $\P_p[N=\infty]=1$ und \emph{Yadin 6.9} für die Trifurkationswahrscheinlichkeit $\P_p[\Psi_r(v)] > 0$ gilt und sei $T_n$ die Anzahl von $r$-Trifurkationspunkten in $S_n$. Aus der Transitivität von $G$ und \emph{Yadin 6.10} folgt: \vspace*{-2mm} $$\Delta(G)^r\cdot|\partial S_n| \geq \E[T_n] = \sum_{s \in S_n} \P_p[\Psi_r(s)] = \sum_{s \in S_n} \P_p[\Psi_r(v)] = |S_n| \P_p[\Psi_r(v)]$$ Insbesondere gilt also $\displaystyle\P_p[\Psi_r(v)] \leq \Delta(G)^r \cdot \frac{|\partial S_n|}{|S_n|} \to 0 \ (n \to \infty)$. \vspace*{2mm} Mit der Umkehrung von \emph{Yadin 6.9} und $\sigma$-Additivität folgt aus $\exists x \in V(G) : \P_p[\Psi_r(x)] = 0$, dass $\P_p[N=\infty]=0$ gilt. Somit ist die Anzahl unendlicher Cluster fast sicher nicht unendlich. Wir können also die Aussage von \emph{Yadin 6.1} (0-1-$\infty$-Gesetz) für amenable Graphen auf $0$ und $1$ beschränken. \end{proof} \end{document}