Die Ramseyzahl R(4,4) < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 12:46 Sa 21.06.2008 | | Autor: | DerAntiPro |
| Aufgabe | | Bestimmen Sie die Ramsey-Zahl R(4,4). |
Also ich soll wie gesagt, die Ramsey-Zahl R(4,4) bestimmen, also diejenige Zahl n, so dass für jeden Graph [mm] G_{n} [/mm] mit n Knoten gilt: [mm] G_{n} [/mm] enthält den [mm] K_{4} [/mm] (der vollständige Graph mit 4 Knoten) oder das Komplement von [mm] G_{n} [/mm] enthält den [mm] K_{4}.
[/mm]
Ich vermute, dass das die 18 ist; für 17 Knoten habe ich einen Graph gefunden, der keinen [mm] K_{4} [/mm] enthält. Ich habe mir den Beweis für R(3,3) = 6 angeschaut und verstanden, da wird mit dem Schubfachschluss argumentiert und ich habe versucht, den Beweis auf R(4,4) zu übertragen, bin aber nicht weitgekommen.
Kann mir jemand weiterhelfen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:23 Sa 21.06.2008 | | Autor: | DerAntiPro |
Ok, ich habs selbst herausbekommen.
LG
|
|
|
|
