Ein halbes Lemma
Ich war so stolz. Letzte Woche habe ich ein erstes Ergebnis produziert, das es tatsächlich in meine Diss schaffen hätte können. Vorerst nur eine Vermutung, aber ich war sicher, dass sich ein Beweis finden lassen würde. Es geht um folgendes:
Wenn ich für einen Graph bestimmte Subgraphen H verbiete, kann dieser Graph dann noch hohen Minimalgrad (delta(G) = cn) und gleichzeitig große chromatische Zahl haben?
Mit anderen Worten: erzwingt die Tatsache, dass es viele Kanten gibt, für diese Graphen eine gute Färbbarkeit? Interessant dabei ist, dass je nach Wahl von H die Antwort auf diese Frage unterschiedlich ausfällt. So ist z.B. bekannt, dass für H = Dreieck gilt: die chromatische Zahl ist unbeschränkt, falls delta(G) < (1/3 – epsilon) n ist und beschränkt, falls delta(G) < (1/3 + epsilon)n. Andererseits wird für H = Fünfkreis vermutet, dass die chromatische Zahl für jeden Minimalgrad der Form cn beschränkt ist.
Meine Lemma hätte etwas über die Situation für Graphen ohne Cliquen auf k Knoten ausgesagt. Dazu gibt es eine gute und eine schlechte Nachricht: die gute ist, dass das Lemma tatsächlich genau so stimmt, wie ich vermutet hatte. Die schlechte ist, dass das schon 1974 von drei Ungarn bewiesen wurde. Wieder nix für die Diss. Aber es bleibt ja noch das Problem für Fünfkreise…
An einem grauen Novemberwochenende haben wir uns das erste Mal getroffen, und sind mit großen Plänen gestartet. Ohne viel Ahnung von AJAX, dafür aber mit viel Spaß am Programmieren sind wir in das Projekt “Browsergame” eingestiegen. Und natürlich sind wir in zwei Tagen nicht weit gekommen. Aber immerhin soweit, dass wir ein weiteres Treffen beschlossen haben. Unser verrücktes Experiment geht am 21./22. Februar in die zweite Runde. Und natürlich sind Mitstreiter herzlich willkommen. Dies gilt besonders für Leute mit graphischem Talent – das fehlt uns wahrscheinlich am meisten. Wer Interesse hat, weiß ja, wie er mich erreichen kann…