Ramseyzahl R(3,4)>8 |
| 06.11.2006, 14:44 | Anna-Lucia | Auf diesen Beitrag antworten » | ||
| Ramseyzahl R(3,4)>8 ich habe ein Problem mit den Ramseyzahlen. Ich soll an einem möglichst übersichtlichen Beispiel zeigen, dass R(3,4)>8 gilt. Ich muss doch zeigen, dass es mehr als 8 Personen geben muss, unter denen mindestens 3 Personen eine Clique oder 4 Personen eine Anticlique bilden. Aber wie mache ich das? Wenn mir einer helfen könnte, wäre ich sehr dankbar. Lieben Gruß Anna-Lucia |
||||
| 06.11.2006, 14:57 | AD | Auf diesen Beitrag antworten » | ||
Indem du einen vollständig gefärbten Graphen mit 8 Knoten angibst, der weder noch enthält. |
||||
| 06.11.2006, 15:37 | Anna-Lucia | Auf diesen Beitrag antworten » | ||
Ich müsste also einen Graphen von 8 Punkten finden, bei dem stets weniger als 3 Punkte eine Clique und weniger als 4 Punkte eine Anticlique bilden? |
||||
| 06.11.2006, 15:42 | AD | Auf diesen Beitrag antworten » | ||
Genau das. Oder etwas anders formuliert: Man kann jede der Kanten so mit rot oder blau färben, dass kein rotes Dreieck (Clique) enthalten ist und kein blaues Tetraeder. |
||||
| 06.11.2006, 15:59 | Anna-Lucia | Auf diesen Beitrag antworten » | ||
So, ich habe einen Graphen mit 8 Punkten gefunden, in dem es nur Cliquen mit weniger als 3 Punkten und nur Anticliquen mit weniger als 4 Punkten gibt. Also, es tauchen in dem Gebilde keine Dreiecke auf und auch keine 4 Punkte, von denen nicht mindestens zwei miteinander verbunden wären. Damit weiß ich, dass R(3,4) nicht 8 sein kann. Muss ich noch zeigen, dass R(3,4) auch nicht kleiner als 8 sein kann oder ist das eh klar? |
||||
| 06.11.2006, 16:11 | Anna-Lucia | Auf diesen Beitrag antworten » | ||
Für Zahlen kleiner als 8 findet man schnell Graphen als Gegenbeispiele, so dass R(3,4)>8 gelten muss. |
||||
| Anzeige | ||||
|
|
||||
| 06.11.2006, 16:52 | AD | Auf diesen Beitrag antworten » | ||
Nein, musst du nicht: Jede Teilmenge der 8 Punkte von deinem 8er-Beispiel erfüllt das, wie man sich leicht überlegen kann. |
||||
| 06.11.2006, 17:25 | Anna-Lucia | Auf diesen Beitrag antworten » | ||
Vielen Dank für deine Hilfe. Gruß Anna-Lucia |
||||
| 06.11.2006, 17:31 | AD | Auf diesen Beitrag antworten » | ||
Mal interessehalber: Welche "Färbung" hast du für deinen Graph genommen? Meines Erachtens müsste es z.B. 12, 23, 34, 45, 56, 67, 78, 81, 15, 26, 37, 48 rot Rest blau erfüllen. Aber es gibt mehrere Möglichkeiten, die hier ist nur ziemlich "symmetrisch". |
||||
|
|