Der Satz von Schur liefert in der Diskreten Mathematik Aussagen, wie groß eine Zahlenmenge sein muss, damit für jede beliebige -Färbung dieser stets eine einfarbige Lösung existiert. Dieser Satz war ursprünglich ein Hilfssatz in einer Veröffentlichung von Issai Schur im Jahre 1916 gewesen.[1] Dabei war Schur gar nicht darauf aus, die Färbung von Punkten in der Ebene zu untersuchen, sondern vielmehr Fermats letzten Satz (welcher erst durch einen Beweis im Jahre 1995 zum Satz wurde). Obwohl zwölf Jahre vor Ramsey gefunden, gilt er als erster Satz der Ramseytheorie.[2]

Formulierung des Satzes

Bearbeiten

Hintergrund

Bearbeiten

Im Satz werden Färbungsprobleme der Ebene betrachtet. Sei   eine einfache Ebene und   die Menge aller Punkte der Ebene mit positiven ganzzahligen Koordinaten. Beispielsweise   und  , wobei diesmal   und   nicht zwangsweise verschieden sein müssen. Nun wird eine endliche Menge Farben gewählt und jeder natürlichen Zahl eine Farbe zugeordnet.

Danach werden alle Punkte   genau dann mit der entsprechenden Farbe eingefärbt, wenn die Färbung von   und   auf dem Zahlenstrahl identisch ist. Alle so nicht berücksichtigten Punkte werden mit einem   markiert. Es bleibt die Frage, ob die Existenz eines gefärbten Punktes gesichert ist, oder die Möglichkeit besteht, jeden Punkt der Ebene mit einem   zu markieren. In anderen Worten, ob eine Färbung für   existiert, so dass kein Punkt   farbig ist. Diese Frage beantwortet der Satz von Schur.

Für jedes   existiert ein kleinstes  , so dass für jede  -Färbung von   eine einfarbige Lösung zu   existiert.

Es sei  . Der Satz von Ramsey sichert die Existenz der Zahl  , für eine beliebige  -Färbung des vollständigen Graphen   mit   Knoten, die Existenz eines einfarbigen Dreiecks. Wir wählen unsere Färbung wie folgt. Die Knoten des   werden mit   durchnummeriert und die Menge   in   disjunkte Teilmengen zerlegt. Diese Mengen sollen den   Farben entsprechen. Nun wird die Kante, die die Knoten   und   verbindet mit der Farbe der Menge eingefärbt, der   angehört. Nach Ramsey’s Theorem existiert in dem Graphen ein einfarbiges Dreieck und dessen Ecken seien  . Dann folgt, da   und   einfarbig sind. Mit   und   gilt dann  . Damit ist der Satz bewiesen.

Verallgemeinerung

Bearbeiten

Neben dem Satz von Rado kann eine Verallgemeinerung erreicht werden, wenn statt der Gleichung   die Gleichung   betrachtet wird.

Sei   und für jedes   sei  . Dann existiert eine kleinste Zahl  , so dass jede  -Färbung von   wenigstens ein   existiert, dass eine Lösung   der Farbe   existiert.

Eine andere Verallgemeinerung untersucht die Gleichung  . Die kleinste Zahl  , so dass jede 2-Färbung von   ein einfarbiges pythagoräisches Tripel zulässt, ist  .[3][4]

Spezialisierung

Bearbeiten

Für den originalen und für den verallgemeinerten Fall kann jeweils untersucht werden, ob die Existenz dieser Zahlen vorliegt, wenn zusätzlich verlangt wird, dass zunächst   und im verallgemeinerten Fall   für   ist. Vor allem in diesem Gebiet wurden bisher nur wenige obere und untere Schranken untersucht.

Sonstiges

Bearbeiten
  • Die Zahlen   werden Schur-Zahlen genannt.
  • Die Zahlen   heißen allgemeine Schur-Zahlen.
  • Die Tripel  , die obigem Satz genügen heißen Schur-Tripel.
  • Die  -Tupel der Verallgemeinerung   heißen Schur-t-Tupel.
  • Der Satz von Rado stellt eine Verallgemeinerung des Schurschen Theorems dar.

Während bei den Schurschen Zahlen sich der Forschungsschwerpunkt auf die Bestimmung von Schranken bezieht, interessiert bei den Tupeln die Anzahl, also wie viele der Tupel für   existieren.

Einzelnachweise

Bearbeiten
  1. Issai Schur: Über die Kongruenz   In: Jahresbericht der DMV. Bd. 25. Teubner, Stuttgart 1917, S. 114–117.
  2. Bruce M Landman, Aaron Robertson: Ramsey Theory on the Integers. AMS, Rhode Island 2004, S. 199–200.
  3. Heule, Kullmann, Marek: Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer
  4. Nature News: Two-hundred-terabyte maths proof is largest ever

Literatur

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