EuroGIGA_Varianten von Erdös-Szekeres Problemen auf gefärbten Punktmengen und kompatible Graphen

Fragen über geometrische Graphen sind eines der zentralen Themen des EUROCORES Programmes EuroGIGA. Innerhalb dieses Programmes konzentriert sich das gemeinsame Forschungsprojekt ComPoSe auf kombinatorische Fragestellungen zu Graphen und geometrischen Objekten. Das gegenständliche Projekt ist ein Teil davon und besteht aus zwei Abschnitten. Im Jahr 1935 formulierten Erdös und Szekeres folgendes Existenzproblem: Gibt es eine Zahl g(k), sodaß jede Punktmenge S mit zumindest g(k) Punkten, in allgemeiner Lage (keine drei Punkte liegen auf einer gemeinsamen Geraden) in der Ebene, eine Teilmenge von k Punkten enthält, die ein konvexes k-Eck bilden? Später wurde diese Frage von Erdös und Guy verallgemeinert: Was ist die Mindestanzahl von konvexen k-Ecken, die eine Menge von n Punkten aufspannt? Beide Varianten stellten sich als äußerst schwierig heraus, und es exisitieren zahlreiche Arbeiten und Teillösungen zu diesen Fragen. In den letzten 75 Jahren sind viele Unterklassen zu diesen Problemen entstanden. In diesem Projekt betrachten wir eine Variante in der die Punkte der gegebenen Menge in Klassen, typischerweise mit verschiedene Farben gekennzeichnet, eingeteilt werden. Ein beispielhaftes Problem hier ist die Frage nach konvexen, leeren, einfärbigen Vierecken: Sei S eine Menge von n Punkten die mit zwei Farben gefärbt ist. Ein durch vier Punkte aus S aufgespanntes Viereck heißt einfärbig, wenn alle Punkte die gleiche Farbe haben, und leer wenn kein anderer Punkt von S im Inneren des Vierecks liegt. Die Frage, die wir untersuchen wollen, lautet: Existiert für jede genügend große Menge von Punkten immer ein leeres, konvexes, einfärbiges Viereck? Verwandte Fragen in höheren Dimensionen sowie Probleme zu gefärbten Varianten der Delaunay Triangulierung werden ebenfalls betrachtet. Die zweite Klasse von Problemen befaßt sich mit kompatiblen Graphen. Eine perfekte, kreuzungsfreie, paarweise Zuordnung (Paarung) für eine Punktmenge mit einer geraden Anzahl von Punkten ist ein planarer Graph in dem jeder Knoten (Punk) Grad 1 hat. Zwei solche Paarungen sind kompatibel, wenn Ihre Vereinigung auf der gemeinsamen Punktmenge ebenfalls planar ist. Darüberhinaus nennt man sie disjunkt, wenn sie keine Kante gemeinsam haben. Wir wollen folgende Vermutung über kompatible Paarungen untersuchen: Zu jeder perfekten Paarung einer Punktmenge mit 4n Punkten existiert eine zweite, kompatible und disjunkte perfekte Paarung. Ähnliche Fragen für Spannpfade, -bäume, -kreise und Pseudo-Triangulierungen werden ebenfalls behandelt. Auch eine duale Variante für Triangulierungen wird untersucht: können für zwei gegebene Punktmengen isomorphe Triangulierungen gefunden werden? Die oben erwähnten Fragestellungen werden als relativ schwer eingestuft. Daher erscheint der erweiterte Rahmen eines kollaborativen europäischen Forschungsprojektes als ausgezeichnet geeignet um diese Fragen erfolgreich bearbeiten zu können.

Fragen über geometrische Graphen sind das zentrale Thema des EUROCORES Programmes EuroGIGA. Innerhalb dieses Programmes konzentrierte sich das internationale Forschungsprojekt ComPoSe auf kombinatorische Fragestellungen zu Graphen und geometrischen Objekten. Unser Team an der TU-Graz hat dabei auch die Gesamtleitung des Projektes ComPoSe übernommen und dabei Forschungsgruppen von 6 weiteren renommierten Europäischen Universitäten koordiniert: Université Libre de Bruxelles, Technische Universität Berlin, Universitat Politècnica de Catalunya Barcelona, Alfréd Rényi Institut of Mathematics Budapest, Charles University Prag und ETH Zürich. In gemeinsamer internationaler Zusammenarbeit konnten viele der ursprünglichen Fragestellungen bearbeitet werden. Beispielhaft sei das im Jahr 1935 von Erdos und Szekeres formulierte Existenzproblem erwähnt: Gibt es eine Zahl g(k), sodass jede Punktmenge S mit zumindest g(k) Punkten in allgemeiner Lage (keine drei Punkte liegen auf einer gemeinsamen Geraden) in der Ebene k Punkten enthält, die ein konvexes k-Eck bilden? Später wurde diese Frage von Erdos und Guy verallgemeinert: Was ist die Mindestanzahl von konvexen k-Ecken, die eine Menge von n Punkten aufspannt? Beide Varianten stellten sich als äußerst schwierig heraus. In einer Reihe von wissenschaftlichen Veröffentlichungen konnten Antworten zu verschiedenen Varianten dieser Frage gegeben werden, so zum Beispiel wenn Punkte mit zusätzlichen Eigenschaften gekennzeichnet sind (gefärbt), oder im höherdimensionalen Raum liegen. Neben der Bearbeitung der ursprünglich gestellten Fragen ist es bei einem internationalen Grundlagenforschungsprojekt immer erfreulich, wenn neue Methoden auf schwierige seit langem offene Probleme angewandt werden können. In einer vielbeachteten Arbeit ist es uns mit amerikanischen, spanischen und mexikanischen Kollegen gelungen, geometrische Konzepte auf topologische Darstellungen von Graphen anzuwenden. Nach über 50 Jahren Forschung stellt dieser Zugang die ersten kombinatorischen Bedingungen zu einer klassischen Vermutung (Harary-Hill conjecture) zur Minimalität von Kreuzungsanzahlen da. Im Forschungsbereich wird nun davon ausgegangen, dass diese Vermutung innerhalb der nächsten 5-10 Jahre endgültig gelöst werden kann. Besonders erfreulich ist auch, dass die durch das gemeinsame Forschungsprojekt entstandenen Kooperationen auch nach dem Auslaufen des Projektes weitergeführt werden und bereits mehrere Folgearbeiten im Entstehen sind.