Computer-gesttzte Beweismethoden in der extremalen Graphentheorie

Razborov verffentlichte 2007 seine Arbeit ber eine neue Technik, die flag Algebras. Mit diesen knnen viele Bereiche der extremalen Graphentheorie in einem formalen Modell dargestellt werden. Diese Diplomarbeit greift jene Technik auf. So werden in Kapitel 2 die Turn-Dichten und Razborovs Flag Algebras vorgestellt und die Methode an einem Beispiel demonstriert. Da Razborovs Technik auf ein semidefinites Problem fhrt, wird erklrt wie dieses gelst werden kann und ebenfalls wie exakte Lsungen erhalten werden knnen. In Kapitel 3 wird Flagmatic prsentiert. Flagmatic ist ein, von Emil R. Vaughan entwickeltes, Computerprogramm um exakte Schranken von Turn-Dichten zu berechnen beziehungsweise obere Schranken zu approximieren. Die grundliegende Idee ist Razborovs semidefinite Methode aus Kapitel 2. In dieser Arbeit werden die Implementation, die allgemeine Arbeitsweise, die Grundlagen, die Befehle und die Hilfsskripte erlutert, sowie die Arbeitsweise an einigen Beispielen demonstriert. Im abschlieenden Kapitel 4 werden einige Anwendungsbeispiele und -ergebnisse aus zwei Arbeiten von Falgas-Ravry und Vaughan prsentiert. Es wird insgesamt ersichtlich, dass Flagmatic zum Beweisen von Aussagen sehr hilfreich ist und auch genutzt wird. Insgesamt lag der Fokus dieser Diplomarbeit auf der Bereitstellung der Theorie der Flag Algebras und einer Einfhrung in Flagmatic.