Schur-Zahl – Wikipedia
Die Schur-Zahlen 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
[Bearbeiten | Quelltext bearbeiten]Nach dem Satz von Schur sind die wie folgt definiert: Sei eine mit Farben beliebig gefärbte Menge. Dann ist die kleinste Zahl, für die stets nicht zwangsweise verschiedene Zahlen existieren, so dass einfarbig sind und die Gleichung lösen.
Berechnung
[Bearbeiten | Quelltext bearbeiten]Die einzigen bisher bekannten Schur-Zahlen sind die für mit (Folge A030126 in OEIS).
Beispiel s(2)
[Bearbeiten | Quelltext bearbeiten]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 ergibt. Wir wählen die Farben rot und blau und vereinbaren, dass alle roten Zahlen in und alle blauen in enthalten sind. OBdA sei 1 rot, also . Dann folgt aus , dass . , also 4 rot und , so muss die 3 blau sein. Also gilt und . Nun ist aber woraus folgt, dass sein muss. Verbleibt zu zeigen, dass ist. Wir wählen die Mengen wie oben und , wobei sich keine einfarbige Lösung ergibt. muss demnach 5 sein.
Abschätzung
[Bearbeiten | Quelltext bearbeiten]Obere Schranke durch Ramsey-Zahlen
[Bearbeiten | Quelltext bearbeiten]Die Schurzahlen lassen sich für durch die Ramsey-Zahlen abschätzen. Wir leiten aus einer -Färbung von eine -Färbung des ab, indem wir die Ecken des von 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 für die Knoten und . Nun besitzt jede Kante einen Wert aus und wird gemäß eingefärbt. Nach Ramsey existiert für ein einfarbiges Dreieck im , welches nach der Definition unserer Färbung einem einfarbigen Schur-Tripel also der Lösung entspricht. Aus folgt .
Explizite obere Schranke
[Bearbeiten | Quelltext bearbeiten]Die Ramsey-Zahlen erlauben die Abschätzung . Damit ergibt sich für die Schur-Zahlen die explizite Abschätzung .
Untere Schranke
[Bearbeiten | Quelltext bearbeiten]Unter der Voraussetzung, dass gilt . Aus einer geeigneten -Färbung ergibt sich zunächst die Ungleichung . Der Rest erfolgt durch Induktion über und
Literatur
[Bearbeiten | Quelltext bearbeiten]- 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