 12. November
|
|
|
19.November
|
|
Rauf und runter
|
|
Auf- und absteigende Teilfolgen und der Quicksort-Algorithmus...
|
|
|
10.Dezember
|
|
Graphen ohne Kreise, ohne
Dreiecke und mit vielen Farben
|
Im Kapitel über Ramsey-Zahlen, haben wir uns überlegt, wieviele Knoten
ein vollständiger Graph mit roten und blauen Kanten haben muß, damit
er einen blauen K_s oder einen roten K_t enthält. Genau dieselbe
Fragestellung kann auch folgendermassen formuliert werden: wenn die
blauen Kanten wirklich im Graph vorhanden sind, und die roten Kanten
aus dem vollständigen Graph herausgenommen werden, haben die Frage
beantwortet, wieviele Knoten ein Graph mindestens enthalten muß, damit
er entweder einen K_s als Teilgraph enthält, oder aber es eine Menge
von mindestens t Knoten gibt, zwischen denen keine Kante verläuft.
Hier wollen wir nun eine ähnliche Fragestellung betrachten -
allerdings wollen wir nun Bedingungen für die Anzahl Kanten
herleiten...
|
|
|
