Rado-Graph

Der Rado-Graph (auch als Erdős-Rényi-Graph oder Zufallsgraph bezeichnet) ist ein spezieller abzählbar unendlicher Graph, der fast sicher entsteht, wenn jedes Knotenpaar unabhängig und mit Wahrscheinlichkeit ${\tfrac {1}{2}}$ durch eine Kante verbunden wird.

Eine wichtige Erkenntnis ist, dass ein Satz $\varphi$ in der Prädikatenlogik erster Stufe genau dann für fast alle endlichen Graphen gilt, wenn $\varphi$ vom Rado-Graphen erfüllt wird.

Er ist aufgrund von Arbeiten in den 1960er-Jahren nach Richard Rado bzw. Rado, Paul Erdős und Alfréd Rényi benannt, taucht aber schon 1937 bei Wilhelm Ackermann auf.

Definition

Ein Ausschnitt des Rado-Graphen mit den ersten acht Knoten.

Der Rado-Graph ${\mathcal {RG}}$ ist definiert als der (ungerichtete) Graph $(\mathbb {N} ,E),$ wobei zwei Zahlen $i,j\in \mathbb {N}$ mit $j<i$ genau dann durch eine Kante verbunden sind, also $E(i,j)$ gilt, wenn $\mathrm {BIT} (i,j)=1,$ d. h. wenn das $j$-te Bit in der Binärdarstellung von $i$ gleich $1$ ist. Zum Beispiel hat $35$ die Binärdarstellung $100011,$ die an den Stellen $0,1$ und $5$ einen Einser hat; also gilt im Rado-Graphen $E(35,0),E(35,1)$ und $E(35,5).$

Es gibt zahlreiche äquivalente Möglichkeiten, den Rado-Graphen zu definieren, unter anderem durch eine probabilistische Konstruktion: Man nimmt die natürlichen Zahlen $\mathbb {N}$ als Knotenmenge und verbindet jedes Zahlenpaar $\{i,j\}$ mit $i\neq j$ unabhängig und mit Wahrscheinlichkeit ${\tfrac {1}{2}}$ mit einer Kante. Diese Konstruktion liefert fast sicher den Rado-Graphen.

Eigenschaften

Erweiterungseigenschaft

Der Rado-Graph hat die Erweiterungseigenschaft: Für je zwei disjunkte, endliche Teilmengen $U$ and $V$ gibt es einen Knoten $x,$ der zu allen Knoten in $U$ und zu keinem Knoten in $V$ adjazent ist.

Der Rado-Graph besitzt folgende bemerkenswerte Eigenschaft, die sogenannte Erweiterungseigenschaft: Zu je zwei disjunkten, endlichen Knotenmengen $U$ und $V$ gibt es stets einen Knoten $z,$ der zu allen Knoten in $U$ und zu keinem Knoten in $V$ adjazent ist. Formal erfüllt ${\mathcal {RG}}$ für alle $n,m\in \mathbb {N}$ mit $m\leq n$ die Formel

$$EA_{n,m}\equiv \forall x_{1},...,x_{n}\left(\left(\bigwedge \limits _{i\neq j}x_{i}\neq x_{j}\right)\rightarrow \exists z\left(\bigwedge \limits _{i=1}^{n}z\neq x_{i}\land \bigwedge \limits _{i\leq m}E(z,x_{i})\land \bigwedge \limits _{i>m}\neg E(z,x_{i})\right)\right).$$

Das kann man wie folgt leicht einsehen: Seien $U=\{x_{1},...,x_{m}\}$ und $Y=\{x_{m+1},...,x_{n}\}$ disjunkt, dann sei $z$ jene Zahl, die $\mathrm {BIT} (z,x_{i})=1$ für alle $i\in \{1,...,m\}\cup \{\mathrm {max} (U\cup V)+1\}$ erfüllt und deren andere Bits alle $0$ sind. Weil $U$ und $V$ disjunkt sind, ist $z$ wohldefiniert. Nach Konstruktion gilt ${\mathcal {RG}}\models E(z,x_{i})$ für alle $i\in \{1,...,m\}$ und ${\mathcal {RG}}\models \neg E(z,x_{j})$ für alle $j\in \{m+1,...,n\}.$

Betrachte hierzu folgendes Beispiel: Sei $U=\{0,2,3,5\}$ und $V=\{1,4,7\},$ dann hat $z$ die Binärdarstellung $100101101,$ d. h. $\mathrm {BIT} (z,0)=\mathrm {BIT} (z,2)=\mathrm {BIT} (z,3)=\mathrm {BIT} (z,5)=\mathrm {BIT} (z,8)=1,$ wobei $8=\mathrm {max} (U\cup V)+1.$

Eindeutigkeit

Der Rado-Graph ist bis auf Isomorphie der einzige abzählbare Graph, der die Erweiterungseigenschaft besitzt. Um das zu zeigen, seien ${\mathcal {A}}$ und ${\mathcal {B}}$ zwei abzählbare Graphen mit Knotenmengen $A=\{a_{i}\mid i\in \mathbb {N} \}$ bzw. $B=\{b_{j}\mid j\in \mathbb {N} \},$ die die Erweiterungseigenschaft haben. Dann kann man wie folgt einen Isomorphismus $h\colon {\mathcal {A}}\rightarrow {\mathcal {B}}$ mit einer Back-and-forth-Konstruktion bauen: Seien ${\mathcal {A}}_{n}$ und ${\mathcal {B}}_{n}$ zwei endliche, zueinander vermöge eines Isomorphismus $h_{n}\colon {\mathcal {A}}_{n}\rightarrow B_{n}$ isomorphe Subgraphen von ${\mathcal {A}}$ bzw. ${\mathcal {B}}$ und sei $a_{i}$ jenes Element von $A$ mit kleinstem Index, das nicht in $A_{n}$ vorkommt. Weil ${\mathcal {B}}$ die Erweiterungseigenschaft hat, gibt es ein Element $b_{j}\in B\backslash B_{n}$, das zu den Elementen von $B_{n}$ genau dieselben Kanten hat, wie $a_{i}$ zu den entsprechenden Elementen (bezüglich $h_{n}$) in $A_{n}.$ Ergo kann man $h_{n}$ zu einem Isomorphismus $h_{n+1}\colon {\mathcal {A}}_{n+1}\rightarrow {\mathcal {B}}_{n+1}$ durch die Vorschrift $h_{n+1}(a_{i}):=b_{j}$ erweitern, wobei ${\mathcal {A}}_{n+1}:={\mathcal {A}}_{n}\cup \{a_{i}\}$ und ${\mathcal {B}}_{n+1}:={\mathcal {B}}_{n}\cup \{b_{j}\}.$ Anschließend verfährt man völlig analog, um zum Element $b_{k}\in B\backslash B_{n+1}$ mit kleinstem Index ein entsprechendes Element $a_{l}\in A\backslash A_{n+1}$ zu finden und $h_{n+1}$ zu einem Isomorphismus $h_{n+2}\colon {\mathcal {A}}_{n+1}\cup \{a_{l}\}\rightarrow B_{n+1}\cup \{b_{k}\}$ zu erweitern.

Wird abwechselnd jeweils das noch nicht verwendete Element aus $A$ bzw. $B$ mit kleinstem Index auf diese Art hinzufügt, ist schließlich $\textstyle \bigcup _{n\in \mathbb {N} }h_{n}$ ein Isomorphismus zwischen ${\mathcal {A}}$ und ${\mathcal {B}}$.

Logische Theorie

Offensichtlich folgt die Erweiterungseigenschaft bereits aus der Formelmenge $EA:=\{EA_{2k,k}\mid k\in \mathbb {N} \}.$ Wie im vorigen Abschnitt gezeigt, ist $EA$ (zusammen mit der Formel $\forall x\,(\neg E(x,x))\land \forall y\forall z\,(E(y,z)\leftrightarrow E(z,y))$, die besagt, dass die Kantenrelation $E$ irreflexiv und symmetrisch ist) ω-kategorisch, d. h. hat bis auf Isomorphie nur ein abzählbares Modell (nämlich den Rado-Graphen). Aus dem Satz von Löwenheim-Skolem folgt daraus unmittelbar, dass $EA$ eine vollständige Theorie ist. Weil sie des Weiteren axiomatisierbar ist (d. h. rekursiv aufzählbar), ist ihr deduktiver Abschluss aufgrund ihrer Vollständigkeit sogar entscheidbar.

Des Weiteren hat $EA$ Quantorenelimination.

Null-Eins-Gesetz der Prädikatenlogik erster Stufe

Eng verwandt mit dem Rado-Graphen ist das Null-Eins-Gesetz der Prädikatenlogik erster Stufe:

Für jedes $n\in \mathbb {N}$ sei $G_{n}$ die Menge aller nummerierten ungerichteten Graphen mit Knotenmenge $\{1,...,n\}.$ Betrachte eine Gleichverteilung auf $G_{n}$. Für einen Satz $\varphi$ in der Sprache $\{E\}$ der Graphen sei $\mu _{n}(\varphi )$ die Wahrscheinlichkeit, dass $\varphi$ in einem zufällig ausgewählten Graphen aus $G_{n}$ gilt, d. h.

$$\mu _{n}(\varphi )={\frac {|\{G\in G_{n}\colon G\models \varphi \}|}{|G_{n}|}}.$$

Das Null-Eins-Gesetz besagt nun, dass

$$\mu (\varphi ):=\lim _{n\rightarrow \infty }\mu _{n}(\varphi )\in \{0,1\}.$$

Für den Beweis überlegt man sich zuerst Folgendes: Haben zwei Graphen ${\mathcal {A}}$ und ${\mathcal {B}}$ die Erweiterungseigenschaft $EA_{2k,k}$, so folgt daraus unmittelbar, dass der Duplikator das $k$-Runden-Ehrenfeucht-Fraïssé-Spiel auf ${\mathcal {A}}$ und ${\mathcal {B}}$ gewinnt. Nach dem Satz von Ehrenfeucht-Fraïssé bedeutet das, dass in ${\mathcal {A}}$ und ${\mathcal {B}}$ dieselben Sätze vom Quantorenrang $k$ gelten. Nun kann man mit einfachen kombinatorischen Überlegungen und Abschätzungen nachweisen, dass $\mu (EA_{2k,k})=1$ für alle $k\in \mathbb {N}$ gilt. Also gelten für jedes $k\in \mathbb {N}$ in fast allen Graphen dieselben Sätze vom Quantorenrang $k.$ Daraus folgt sofort das Null-Eins-Gesetz, denn jeder Satz hat einen solchen Quantorenrang.

Weil insbesondere der Rado-Graph selbst für jedes $k\in \mathbb {N}$ die Erweiterungseigenschaft $EA_{2k,k}$ hat, gilt für jeden Satz $\varphi$

$${\mathcal {RG}}\models \varphi \iff \mu (\varphi )=1.$$

Da die Theorie von ${\mathcal {RG}}$ entscheidbar ist, ist also auch das Berechnungsproblem, welche Sätze in fast allen Graphen gelten, entscheidbar.

Das Null-Eins-Gesetz lässt sich leicht auf beliebige relationale Sprachen verallgemeinern.

Literatur

• Leonid Libkin: Elements of Finite Model Theory, Springer Verlag, 2004, ISBN 9783662070031.
• Wilfrid Hodges: Model Theory (Encyclopedia of Mathematics and its Applications), Cambridge University Press, 1993, ISBN 9780511551574.