Homogene Mengen in kombinatorischen Strukturen mit lokalen Einschränkungen

• Antragstellerin: Professorin Maria Axenovich, Ph.D.
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung seit 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 455779225

Eine der wesentlichen Aufgaben der extremalen Kombinatorik besteht darin, das Verhalten homogener Mengen, wie Cliquen in Graphen und Ketten in Partialordnungen  (Posets), zu verstehen.   Erdös und Hajnal beobachteten, dass das Verbot eines festen induzierten Untergraphen einen Graphen zwingt, eine "große" homogene Menge zu haben, die viel größer ist, als man zum Beispiel in einem Zufallsgraph beobachten würde. Dies initiierte ein Forschungsprogramm  mit dem Ziel zu quantifizieren, wie die Größe einer größten homogenen Menge von lokalen Beschränkungen abhängt. Dieser Antrag befasst sich mit zwei spezifischen Aspekten dieses Forschungsprogramms:1. Die Identifikation großer homogener Mengen in mehrfarbigen Graphen mit einem festen verbotenen Farbmuster, und 2. Die Bestimmung großer homogener Mengen in Posets mit einer Subposet-Einschränkung.  Der innovative Aspekt an diesem Antrag ist, dass anstelle der üblichen Untersuchung von  Graphen  (die vollständigen Graphen mit zwei Farben kantengefärbt entspricht) die Färbung von Graphen im Fall  einer großen Anzahl von Farben untersucht wird.  Angesichts der Tatsache, dass diese Einstellung bislang nicht systematisch untersucht wurde, verspricht sie nicht nur allgemeine Aussage zu liefern, sondern auch Licht auf die klassische Zweifarbenfrage zu werfen. Darüber hinaus wird hier vorgeschlagen, eine eng verwandte Frage zu untersuchen, nämlich verbotene Muster zu finden, die ein spezifisches asymptotisches Verhalten von größten homogenen Mengen garantieren.  Nach unserem bestem Wissen  wurde der Erdös-Hajnal Satz für teilweise geordnete Mengen bislang nicht behandelt.  Spezielle Unterprobleme entsprechen hier Fragen vom Ramsey-Typ für Boolesche Gitter. Diese Fragestellungen sind bislang wenig verstanden. Es sind nur wenige, relativ schwache Schranken bekannt. Die Beantwortung der vorgeschlagenen Fragen für Posets wird nicht nur das Verhalten großer homogener Mengen behandeln, sondern auch das Verständnis der Struktur von Posets mit verbotenen Unterposets ermöglichen; damit wird in gewisser Weise die Turán-Ramsey-Theorie auf Posets erweitert. Die vorgeschlagene Forschung soll Wissenslücken in diesen beiden eng miteinander verbundenen Bereichen beseitigen.  Dabei wird vorgeschlagen, Werkzeuge der strukturellen Kombinatorik, die spezifische Beschreibungen von diskreten Objekten unter Vermeidung fester Substrukturen liefern. Hier sollen leistungsfähige Werkzeuge der Theorie extremer Graphen und der Kombinatorik kombiniert werden.

• DFG-Verfahren: Sachbeihilfen