Andi on-line

Natürlich sind wir nicht nur zum Vergnügen hier. Während der Konferenz haben wir jeden Tag zwei Vortragsblöcke, die wiederum jeweils einen “invited talk” und sechs Konferenzbeiträge enthalten. Der eingeladene Referent ist demnach eine Koryphäe (So schreibt man das also?) in seinem Gebiet, und sein Vortrag zeigt die großen Konzepte, an denen gerade gearbeitet wird. Demgegenüber sind die Konferenzbeiträge oft von Nachwuchsforschern, die Detailergebnisse präsentieren oder manchmal auch nur Detailfragen, die noch nicht gelöst sind.
Graphentheorie ist ein weites Gebiet, weshalb ich von den meisten Themen nicht viel Ahnung habe und wohl auch nie haben werde. Aber manchmal ist doch etwas interessantes dabei – und wenn es die Persönlichkeit gewisser Vortragender ist. Wirklich mühsam wird es nur, wenn die Japan-Fraktion über Einbettungen von Triangulierungen auf Flächen höheren Geschlechts berichtet. Das kann aber auch an unserer unterschiedlichen Auffassung von “Was ist Englisch?” liegen.

Jaroslav Nesetril bei seinem Vortrag über Structural Properties of Sparse Graphs – den Mann muss man einfach sympathisch finden.
Und hier noch ein kleines Problem, das ich mitgenommen habe:

Wir nehmen die Menge der natürlichen Zahlen als Knoten eines Graphs und fügen Kanten genau zwischen den Knotenpaaren der Form ( a+b, ab ) ein. Welche chromatische Zahl hat der so erzeugte Graph?

Bisher ist keine Lösung bekannt. Was man schnell sieht ist, dass der Graph nicht 2-färbbar sein kann:
10 = 5+5, 25 = 5*5, also gibt es eine Kante zwischen 10 und 25. Weiter ist
10 = 4+6, 24 = 4*6, also gibt es eine Kante zwischen 10 und 24. Und schließlich:
25 = 1+24, 24 = 1*24, was eine Kante zwischen 24 und 25 bedeutet.
Wir erhalten also ein Dreieck, das nicht mit zwei Farben gefärbt werden kann. Aber wie sieht es mit 3-färbbar aus?