FWF - ComPoSe - 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.