1 ¨ Ubungen 8 zur Graphentheorie 2 1. Wie ist n definiert im ersten Beweis von Satz 7.3.1? K¨ onnte es null sein, und wenn ja, wie geht dann der Beweis? 2. Leite die Aussage (⇤) aus dem ersten Beweis von Satz 7.3.1 aus der Aussage des Satzes her (d.h. zeige, dass (⇤) nur formal st¨ arker ist als der Satz selbst). 3. Ist es im zweiten Beweis von Satz 7.3.1 wirklich n¨ otig, in Gk+1 f¨ ur i 2/ i {i1 , i2 } verschiedene disjunkte Kopien von Vk vorzuhalten, oder k¨ onnte man Gk+1 aus Gk gewinnen, indem man nur P durch P 0 ersetzt und dieses durch geschickt gew¨ ahlte Kanten mit den anderen Vik verbindet? 4. Zeige, dass es zu je zwei Graphen H1 , H2 einen Graphen G = G(H1 , H2 ) gibt mit der Eigenschaft, dass G zu jeder Eckenf¨ arbung mit den Farben 1 und 2 einen induzierten H1 der Farbe 1 oder einen induzierten H2 der Farbe 2 enth¨ alt. 5. Zeige, dass der im zweiten Beweis von Satz 7.3.1 konstruierte Ramseygraph G f¨ ur H in der Tat !(G) = !(H) erf¨ ullt. 6.+ Zeige mit dem Satz von Ramsey, dass es zu k, ` 2 N stets ein n 2 N gibt, so dass jede Folge von n verschiedenen ganzen Zahlen eine aufsteigende Teilfolge der L¨ ange k + 1 oder eine absteigende Teilfolge der L¨ ange ` + 1 enth¨ alt. Finde ein Beispiel, das n > k` zeigt. Beweise dann den Satz von Erd˝ os & Szekeres, dass n > k` auch ausreicht. 2 Hinweise 1. Der Wert von n wird implizit definiert, ein wenig sp¨ ater als n zum ersten Mal im Beweis auftaucht. 2. Aus gegebenen H1 und H2 konstruiere ein H, f¨ ur das der Graph G aus Satz 7.3.1 die Eigenschaft (⇤) besitzt. 3. Beweis genau verstehen. 4. G[U ! H]. 5. Zeige !(Gk ) = !(H) induktiv f¨ ur k = 0, . . . , m. 6.+ Die beiden ersten Fragen sind einfach. Zum Beweis des Satzes von Erd˝ os & Szekeres benutze Induktion nach k f¨ ur festes `, und betrachte im Induktionsschritt die letzten Elemente aufsteigender Teilfolgen der L¨ ange k. Alternativ verwende einen Satz aus einem fr¨ uheren Kapitel.