0-1-Gesetze für zufällige Graphen und mathematische Logik

Was ist die Wahrscheinlichkeit, dass ein zufällig gewählter Graph auf $n$ Knoten eine gewisse Eigenschaft $E$ besitzt, etwa dass die Anzahl der Kanten gerade ist oder dass der Graph einen Knoten besitzt, der mit keinem anderen Knoten verbunden ist?
Im Vortrag werde ich erklären, was diese Frage mit Mathematischer Logik zu tun hat. Lässt sich $E$ in der Logik erster Stufe ausdrücken, so strebt die Wahrscheinlichkeit, dass ein zufälliger Graph mit $n$ Knoten
die Eigenschaft $E$ besitzt, stets entweder gegen 0 oder gegen 1, wenn man $n$ beliebig groß werden lässt. Grund hierfür ist, dass es nur einen abzählbar unendlichen Zufallsgraphen $\Gamma$ gibt. Die Konstruktion von $\Gamma$ mit Hilfe der Amalgamierungsmethode von Fraissé sowie seine Eindeutigkeit werde ich im Vortrag skizzieren.

Prof. Dr. Martin Hils (Institut für Mathematische Logik)