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

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

Die einzigen bisher bekannten Schur-Zahlen sind die für   mit   (Folge A030126 in OEIS).

Beispiel s(2)

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

Obere Schranke durch Ramsey-Zahlen

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

Die Ramsey-Zahlen erlauben die Abschätzung  . Damit ergibt sich für die Schur-Zahlen die explizite Abschätzung  .

Untere Schranke

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
  • 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