Schur Zahl Die en s r displaystyle s r sind in der diskreten Mathematik diejenigen Zahlen welche die Bedingung des Satze

Schur-Zahl

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

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele

Veröffentlichungsdatum: Dezember 28, 2023, 11:27 am

Die Schur Zahlen s r displaystyle s r sind in der diskreten Mathematik diejenigen Zahlen welche die Bedingung des Satzes von Schur erfullen und minimal sind Sie geben ein Mass dafur wie gross eine gefarbte Menge mindestens sein muss um stets eine einfarbige Losung zu finden In Farbungsproblemen von Ebenen lassen sich so Aussagen treffen ob gefarbte Mengen existieren fur die keine einfarbige Losung existiert und damit kein Punkt der Ebene gefarbt werden kann Inhaltsverzeichnis 1 Definition 2 Berechnung 2 1 Beispiel s 2 3 Abschatzung 3 1 Obere Schranke durch Ramsey Zahlen 3 2 Explizite obere Schranke 3 3 Untere Schranke 4 LiteraturDefinition BearbeitenNach dem Satz von Schur sind die s r Z displaystyle s r in mathbb Z nbsp wie folgt definiert Sei 1 s r displaystyle 1 s r nbsp eine mit r displaystyle r nbsp Farben beliebig gefarbte Menge Dann ist s r displaystyle s r nbsp die kleinste Zahl fur die stets nicht zwangsweise verschiedene Zahlen x y z 1 s r displaystyle x y z in 1 s r nbsp existieren so dass x y z displaystyle x y z nbsp einfarbig sind und die Gleichung x y z displaystyle x y z nbsp losen Berechnung BearbeitenDie einzigen bisher bekannten Schur Zahlen sind die fur r 1 5 displaystyle r 1 ldots 5 nbsp mit s 1 2 s 2 5 s 3 14 s 4 45 s 5 161 displaystyle s 1 2 s 2 5 s 3 14 s 4 45 s 5 161 nbsp Folge A030126 in OEIS Beispiel s 2 Bearbeiten s 2 5 displaystyle s 2 5 nbsp besagt dass fur eine Farbung des positiven Zahlenstrahls ab der 1 mit zwei Farben wenigstens 5 Zahlen eingefarbt werden mussen damit sich in jedem Fall eine einfarbige Losung fur x y z displaystyle x y z nbsp ergibt Wir wahlen die Farben rot und blau und vereinbaren dass alle roten Zahlen in R displaystyle R nbsp und alle blauen in B displaystyle B nbsp enthalten sind OBdA sei 1 rot also 1 R displaystyle 1 in R nbsp Dann folgt aus 1 1 2 displaystyle 1 1 2 nbsp dass 2 B displaystyle 2 in B nbsp 2 2 4 displaystyle 2 2 4 nbsp also 4 rot und 1 3 4 displaystyle 1 3 4 nbsp so muss die 3 blau sein Also gilt R 1 4 displaystyle R 1 4 nbsp und B 2 3 displaystyle B 2 3 nbsp Nun ist aber 1 4 5 2 3 displaystyle 1 4 5 2 3 nbsp woraus folgt dass s r 5 displaystyle s r leq 5 nbsp sein muss Verbleibt zu zeigen dass s r 5 displaystyle s r geq 5 nbsp ist Wir wahlen die Mengen wie oben R 1 4 displaystyle R 1 4 nbsp und B 2 3 displaystyle B 2 3 nbsp wobei sich keine einfarbige Losung ergibt s r displaystyle s r nbsp muss demnach 5 sein Abschatzung BearbeitenObere Schranke durch Ramsey Zahlen Bearbeiten Die Schurzahlen lassen sich fur r 1 displaystyle r geq 1 nbsp durch s r R 3 r 1 displaystyle s r leq R 3 r 1 nbsp die Ramsey Zahlen abschatzen Wir leiten aus einer r displaystyle r nbsp Farbung x displaystyle chi nbsp von 1 n 1 displaystyle 1 n 1 nbsp eine r displaystyle r nbsp Farbung des K n displaystyle K n nbsp ab indem wir die Ecken des K n displaystyle K n nbsp von 1 n displaystyle 1 ldots n nbsp durchnummerieren und anschliessend dessen Kanten farben Dabei gehen wir so vor dass jede Kante den Betrag der Differenz seiner beiden inzidenten Punkte zugewiesen bekommt also j i displaystyle j i nbsp fur die Knoten i displaystyle i nbsp und j displaystyle j nbsp Nun besitzt jede Kante einen Wert aus 1 n 1 displaystyle 1 n 1 nbsp und wird gemass x displaystyle chi nbsp eingefarbt Nach Ramsey existiert fur n R 3 r displaystyle n R 3 r nbsp ein einfarbiges Dreieck im K n displaystyle K n nbsp welches nach der Definition unserer Farbung einem einfarbigen Schur Tripel also der Losung entspricht Aus n R 3 r displaystyle n R 3 r nbsp folgt s r n 1 R 3 r 1 displaystyle s r leq n 1 R 3 r 1 nbsp Explizite obere Schranke Bearbeiten Die Ramsey Zahlen erlauben die Abschatzung R 3 r 3 r displaystyle R 3 r leq 3r nbsp Damit ergibt sich fur die Schur Zahlen die explizite Abschatzung s r 3 r 1 displaystyle s r leq 3r 1 nbsp Untere Schranke Bearbeiten Unter der Voraussetzung dass r 1 displaystyle r geq 1 nbsp gilt s r 3 r 1 2 displaystyle s r geq frac 3 r 1 2 nbsp Aus einer geeigneten r 1 displaystyle r 1 nbsp Farbung ergibt sich zunachst die Ungleichung s r 1 3 s r 1 displaystyle s r 1 geq 3s r 1 nbsp Der Rest erfolgt durch Induktion uber r displaystyle r nbsp und s 1 2 3 1 1 2 displaystyle s 1 2 geq frac 3 1 1 2 nbsp Literatur BearbeitenRonald 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 Abgerufen von https de wikipedia org w index php title Schur Zahl amp oldid 220138608