Ramsey-Zahlen

Silvester steht vor der Tür. Auf so einer Silvesterparty sehen sich manche Gäste zum ersten mal und kannten sich vorher nur über Ecken. Es gibt also unterschiedlich große Gruppen von einander Bekannten und Gruppen von einander Fremden. Wie groß können diese Gruppen sein? Oder genauer gesagt, wie groß muss die Anzahl der Gäste überhaupt sein, damit es auf jeden Fall eine Gruppe von $n$ Bekannten oder eine Gruppe von $m$ Fremden gibt? (Beides gleichzeitig können wir natürlich nicht erwarten.) Oder gibt es überhaupt so eine Anzahl? Das Theorem von Ramsey sagt, dass es tatsächlich eine solche Anzahl gibt. Die Mindestanzahl von benötigten Gästen wird als Ramsey-Zahl $R(n,m)$ definiert. Bis heute sind nur relativ wenige konkrete Werte von $R(n,m)$ bekannt. Es gilt zum Beispiel $R(4,4)=18$, was bedeutet, dass es auf einer Party mit $18$ Gästen (aber nicht unbedingt auf einer Party mit $17$ Gästen) auf jeden Fall $4$ Bekannte oder $4$ Fremde gibt. Dieser Artikel gibt eine kurze Einführung in Ramsey-Zahlen.

Für feste natürliche Zahlen $n,p,q$ bestimmen wir die Anzahl der Abbildungen $f : \{1,\dotsc,n\} \to \{1,\dotsc,n\}$ mit $f^p = f^q$, wobei $f^p$ die $p$-fache Verkettung von $f$ sei. Wir leiten insbesondere für festes $p \geq 2$ und $q=1$ die erzeugende Funktion $\exp(\sum_{d ~\mid~ p-1} \frac{1}{d} (z \cdot \exp(z))^d)$ für die Anzahlen her. Am Ende zeigen wir eine alternative Herleitung auf, die mit kombinatorischen Spezies arbeitet. Das folgende Bild zeigt zum Beispiel eine Abbildung $f$ mit $f^6=f^2$.

Galois-Verbindungen

Ausgehend von einer einfachen Beobachtung zwischen der Bildmenge und der Urbildmenge gelangen wir zum Begriff einer Galois-Verbindung. Dieser wird in diesem Artikel untersucht. Wir beweisen einfache Eigenschaften von Galois-Verbindungen und geben ein paar einfache Anwendungen an. Insbesondere finden wir damit einen konzeptionellen Beweis für eine ganze Reihe von Charakterisierungen von injektiven bzw. surjektiven Abbildungen. Im letzten Abschnitt zeigen wir dann die Nützlichkeit von Galois-Korrespondenzen auf, wofür der Hauptsatz der Galoistheorie das prominenteste Beispiel ist. Abgesehen von den Beispielen sind für das Verständnis dieses Artikels lediglich Grundbegriffe der Mengenlehre und der Ordnungstheorie nötig.