Satz von Schur

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 | Quelltext bearbeiten]

Hintergrund[Bearbeiten | Quelltext 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.

Satz[Bearbeiten | Quelltext bearbeiten]

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

Beweis[Bearbeiten | Quelltext bearbeiten]

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 | Quelltext 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 das 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 | Quelltext 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 | Quelltext bearbeiten]

  • Die Zahlen werden Schurzahlen genannt.
  • Die Zahlen heißen allgemeine Schurzahlen.
  • Die Tripel , die obigem Satz genügen heißen Schurtripel.
  • 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 | Quelltext 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 | Quelltext 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.