Schur-Zahl

Die Schur-Zahlen $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 Schur-Zahlen sind die für $r=1\ldots 5$ mit $s(1)=2,s(2)=5,s(3)=14,s(4)=45,s(5)=161$ (Folge A030126 in OEIS).

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ärbt 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 Ramsey-Zahlen

Die Schurzahlen lassen sich für $r\geq 1$ durch $s(r)\leq R(3;r)-1$ die Ramsey-Zahlen abschätzen. Wir leiten aus einer $r$ -Färbung $\chi$ 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äß $\chi$ 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 Schur-Tripel also der Lösung entspricht. Aus $n=R(3;r)$ folgt $s(r)\leq n-1=R(3;r)-1$ .

Explizite obere Schranke

Die Ramsey-Zahlen erlauben die Abschätzung $R(3;r)\leq 3r!$ . Damit ergibt sich für die Schur-Zahlen 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}}.$

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.