Zusammenhang und Baumstruktur in Graphen und Matroiden

• Antragsteller: Professor Dr. Reinhard Diestel
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2014 bis 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 248688805

Ein altes Problem der Graphentheorie beschäftigt sich mit der Frage, ob man in jedem Graphen eine Grobstruktur identifizieren kann, die beschreibt, wie sich die hochzusammenhängenden Teile des Graphen zur Gesamtstruktur zusammenfügen. Kann man etwa in jedem (k-1)-zusammenhängenden Graphen eine grobe Baumstruktur ausmachen, die im wesentlichen die `k-zusammenhängenden Blöcke' des Graphen als Teile hat?Für k=2 ist die Antwort klar: Die 2-zusammenhängenden Teilgraphen und die `Brücken' eines zusammenhängenden Graphen bilden zusammen in einfacher Weise eine Baumstruktur, den sogenannten `block-cutvertex tree'. Für k=3 gibt es aus den sechziger Jahren ein ähnliches, jedoch wesentlich komplizierteres, Resultat von Tutte. Für größeres k gibt es zwei unterschiedliche Ansätze, die jeweils einen wichtigen Teilaspekt höheren Zusammenhangs zur Grundlage haben. Im Jahre 1991 konnten Robertson und Seymour zeigen, dass für jeden endlichen Graphen eine Baumzerlegung existiert, deren Teile je genau ein `Tangle der Ordnung k' beheimaten. Während der letzten zehn Jahre konnten Geelen, Gerards, Robertson und Whittle diese und weitere Resultate über Tangles in Graphen auch auf endliche Matroide übertragen. Dunwoody und Krön haben vor kurzem einen zweiten Ansatz vorgestellt, der auf die von Mader 1971 eingeführten k-untrennbaren Mengen zurückgreift. Sie konzipieren eine allgemeinere axiomatische Theorie der `vertex-cuts' mit deren Hilfe sie zeigen, dass man einen (k-1)-zusammenhängenden Graphen baumartig so zerlegen kann, dass die verschiedenen maximalen (k-1)-untrennbaren Mengen, die sogenannten k-Blöcke, in verschiedenen Teilen der Baumstruktur enthalten sind. In einem eigenen Ansatz konnten wir kürzlich diese Resultate von Dunwoody und Krön neu beweisen, auf nicht notwendigerweise (k-1)-zusammenhängende endliche Graphen erweitern, und die Baumstrukturen für verschiedene Werte von k in einer gemeinsamen Baumzerlegung abbilden. Wir verwenden hierbei ausschliesslich Standardbegriffe der Graphentheorie, wie z.B. Baumzerlegungen, und kommen ohne eine axiomatische Theorie aus.Ziel dieses Projektes ist es:- die innere Struktur jener Teile der Baumzerlegung die einen k-Block enthalten zu verstehen, insbesondere in welcher Weise ein k-Block in den ihn enthaltenen Teil eingebettet ist;- den Begriff des k-Blocks und den des Tangles zu einem neuen allgemeineren Begriff zusammenzufassen, und die Existenz einer entsprechenden Baumzerlegung nachzuweisen, um so alle oben genannten Ergebnisse zu vereinheitlichen und zu erweitern;- einen solchen neuen Begriff, und die Konstruktion einer entsprechenden Baumzerlegung, von Graphen auf Matroide zu übertragen;- die gesamte Theorie auf unendliche Graphen und Matroide zu übertragen.

• DFG-Verfahren: Sachbeihilfen