Schurzahlen

Die Schurzahlen s(r) sind in der diskreten Mathematik diejenigen Zahlen, welche die Bedingung des Satzes von Schur erfüllen und minimal sind. Sie geben ein Maß dafür, wie groß eine gefärbte Menge mindestens sein muss, um stets eine einfarbige Lösung zu finden. In Färbungsproblemen von Ebenen lassen sich so Aussagen treffen, ob gefärbte Mengen existieren, für die keine einfarbige Lösung existiert und damit kein Punkt der Ebene gefärbt werden kann.

Definition

Nach dem Satz von Schur sind die $s(r)\in \mathbb{Z}^+$ wie folgt definiert: Sei [1,s(r)] eine mit r Farben beliebig gefärbte Menge. Dann ist s(r) die kleinste Zahl, für die stets nicht zwangsweise verschiedene Zahlen $x,y,z \in [1,s(r)]$ existieren, so dass x,y,z einfarbig sind und die Gleichung x + y = z lösen.

Berechnung

Die einzigen bisher bekannten Schurzahlen reichen für $r = 1 \ldots 4$ mit s(1) = 2,s(2) = 5,s(3) = 14,s(4) = 45.

Beispiel s(2)

s(2) = 5 besagt, dass für eine Färbung des positiven Zahlenstrahls ab der 1 mit zwei Farben, wenigstens 5 Zahlen eingefärben werden müssen, damit sich in jedem Fall eine einfarbige Lösung für x + y = z ergibt. Wir wählen die Farben rot und blau und vereinbaren, dass alle roten Zahlen in R und alle blauen in B enthalten sind. OBdA sei 1 rot, also $1\in R$. Dann folgt aus 1 + 1 = 2, dass $2 \in B$. 2 + 2 = 4, also 4 rot und 1 + 3 = 4, so muss die 3 blau sein. Also gilt R = {1,4} und B = {2,3}. Nun ist aber 1 + 4 = 5 = 2 + 3 woraus folgt, dass $s(r) \leq 5$ sein muss. Verbleibt zu zeigen, dass $s(r) \geq 5$ ist. Wir wählen die Mengen wie oben R = {1,4} und B = {2,3}, wobei sich keine einfarbige Lösung ergibt. s(r) muss demnach 5 sein.

Abschätzung

Obere Schranke durch Ramseyzahlen

Die Schurzahlen lassen sich für $r \geq 1$ durch $s(r) \leq R(3;r)-1$ die Ramseyzahlen abschätzen. Wir leiten aus einer r-Färbung χ von [1,n − 1] eine r-Färbung des K_n ab, indem wir die Ecken des K_n von $1\ldots n$ durchnummerieren und anschließend dessen Kanten färben. Dabei gehen wir so vor, dass jede Kante den Betrag der Differenz seiner beiden inzidenten Punkte zugewiesen bekommt, also | j − i | für die Knoten i und j. Nun besitzt jede Kante einen Wert aus [1,n − 1] und wird gemäß χ eingefärbt. Nach Ramsey existiert für n = R(3;r) ein einfarbiges Dreieck im K_n, welches nach der Definition unserer Färbung einem einfarbigen Schurtripel also der Lösung entspricht. Aus n = R(3;r) folgt $s(r) \leq n-1 = R(3;r) - 1$.

Explizite obere Schranke

Die Ramseyzahlen erlauben die Abschätzung $R(3;r) \leq 3r!$. Damit ergibt sich für die Schurzahlen die explizite Abschätzung $s(r) \leq 3r! - 1$.

Untere Schranke

Unter der Voraussetzung, dass $r \geq 1$ gilt $s(r) \geq \frac{3^r+1}{2}$. Aus einer geeigneten r + 1-Färbung ergibt sich zunächst die Ungleichung $s(r+1) \geq 3s(r) - 1$. Der Rest erfolgt durch Induktion über r und $s(1) = 2 \geq \frac{3^1 + 1}{2}.$

Vermutung und offene Fragen

Es wurde bisher noch nicht gezeigt, dass s(5) = 120 ist.

Literatur

• Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer: Ramsey Theory. 8. Kapitel, 2. Auflage. Wiley, New York, NY, 1990, ISBN 0-471-50046-1
• Bruce M. Landman, Aaron Robertson: Ramsey Theory on the Integers. 3. Kapitel, 1. Auflage. AMS, Rhode Island, 2004, ISBN 0-8218-3199-2