Bachelor Theses and Master Theses

Ein Graph G mit ungerader Taillenweite (mindestens) 2k + 1 ist ein Graph, der keine Kreise von ungerader Länge kleiner als 2k + 1 besitzt. Diese Arbeit beschäftigt sich mit der Struktur von Graphen mit beliebiger ungerader Taillenweite 2k+1 und großem Minimalgrad. Frühere Arbeiten haben die Struktur von Graphen mit ungerader Taillenweite 5 und hohem Minimalgrad hinreichend charakterisiert. Als erstes wird eine Zusammenfassung der Kette dazu beitrageneder Ergebnisse gegeben. Einfach formuliert lautet das Hauptresultat: Jeder Graph von Ordnung n mit ungerader Taillenweite 5 und Minimalgrad > n/3 ist 4-färbbar und homomorph mit einem Graphen aus zwei unendlichen Folgen von Graphen. Weiterhin ist eine neue Charakterisierung einer bestimmten Klasse von Teilgraphen (die "generalized pentagons"), die in Graphen mit ungerader Taillenweite 5 und großem Minimalgrad enthalten sind, gegeben. Die wenigen Resultate für Graphen mit ungerader Taillenweite 7 und beliebiger ungerader Taillenweite 2k + 1 für k > 3 werden dann präsentiert. Im Anschluss folgt das Hauptergebnis dieser Arbeit, eine Bestätigung einer Vermutung von Albertson, Chan, and Haas, die besagt: jeder Graph von Ordnung n mit ungerader Taillenweite 2k + 1 und Minimalgrad mindestens 3n/4k ist entweder homomorph dem (2k + 1)-Kreis oder kann durch eine Reihe von Ecken-Duplikationen der Möbiusleiter mit 2k Sprossen erhalten werden. Ein maximaler Graph mit ungerader Taillenweite 2k + 1 ist ein Graph mit ungerader Taillenweite 2k + 1 zu dem keine Kante hinzugefügt werden kann ohne einen ungeraden Kreis von Länge kleiner als 2k + 1 zu erzeugen. Solche maximalen Graphen sind von zentraler Bedeutung im Beweis des Hauptergebnisses, da die wichtigsten mathematischen Werkzeuge in den nachfolgenden Beobachtungen einfache Eigenschaften von maximalen Graphen mit ungerader Taillenweite 2k + 1 sind.

Die Diplomarbeit beschäftigt sich mit der numerischen Approximation stabiler und instabiler Invarianzkurven von Poincaré-Abbildungen dynamischer Systeme. Bei periodisch erregten Systemen lassen sich in der Regel mehrere stabile Lösungen bestimmen. Nun stellt sich bei gegebener Anfangslösung die Frage, auf welche dieser Lösungen sich das System einschwingt. Dazu sollen mit der Fortsetzungsmethode von Philippow die Grenzen der Einzugsgebiete (die so genannten Separatrizen) stabiler periodischer Lösungen numerisch approximiert werden. Mit Hilfe eines selbst entwickelten Matlab-Programms soll das Lösungsverhalten periodisch erregter Systeme der Dimension˜2 geklärt werden. Der Fortsetzungs-Algorithmus knüpft an die langjährige Forschungsarbeit auf diesem Gebiet an und verbessert ein bereits bestehendes Programm.

Bei der Betrachtung von Lernverfahren für wiederholte Normalformspiele ergibt sich die Frage nach solchen Verfahren, die in einem beliebigen, fest vorgegebenen Spiel fast sicher gegen ein vorhandenes Nash-Gleichgewicht konvergieren. - In der Arbeit wird gezeigt, welche Voraussetzungen dafür erfüllt sein müssen und wie ein solches Lernverfahren konstruiert werden kann. Darüber hinaus wird bewiesen, dass die ermittelten Voraussetzungen notwendig sind für die Existenz eines Lernverfahrens. Zu diesem Zweck wird die Problemstellung in eine Begriffswelt überführt, welche die Diskussion der Lernverfahren als Algorithmus veranschaulicht.

Differential-algebraische Gleichungen gewinnen in vielen technischen Gebieten, wie zum Beispiel der Elektrotechnik, immer mehr an Bedeutung. Da sie in den meisten Fällen aber nicht explizit lösbar sind, oder schwer handhabbare Lösungen besitzen, konzentriert man sich auf qualitative Aussagen über das Systemverhalten. In dieser Arbeit wird daher die asymptotische Stabilität linearer, homogener, differential-algebraischer Gleichungen mit konstanten Koeffizienten-Matrizen ausführlich untersucht und notwendige sowie hinreichende Bedingungen für diese angegeben. In diesem Zusammenhang wird die Lösbarkeit der sogenannten verallgemeinerten Lyapunov-Gleichung sowie die Eindeutigkeit und Darstellung der Lösung analysiert werden. Als Grundlage dient die Lösungstheorie differential-algebraischer Gleichungen. Im Anhang befindet sich diesbezüglich eine vermutlich neue Darstellungsform der Lösungen mittels verallgemeinerter Hauptvektoren.

In dieser Diplomarbeit betrachten wir ein Problem, welches von Golumbic, Peled und Rotics aufgeworfen wurde. Es behandelt das Verhältnis zwischen einem Komplexitätsmaß für Boolesche Funktionen und einer Problematik der Graphenüberdeckung. Genauer gesagt, setzt das Problem die sogenannte Readability von monotonen Booleschen Funktionen in Verbindung mit Kantenüberdeckungen von Graphen, die solchen Funktionen zugeordnet werden, durch Kantenmengen vollständiger bipartiter Teilgraphen. - Eine monotone Boolesche Funktion hat eine Readability von höchstens k, wenn sie durch eine Formel dargestellt werden kann, in welcher jede Variable höchstens k mal vorkommt. Wir ordnen einer monotonen Booleschen Funktion F einen Graph G zu, dessen Knotenmenge die Menge von Variablen von F ist und die Minimalterme von F genau den maximalen Cliquen von G entsprechen. - Golumbic et al. stellten die Frage, ob jede monotone Boolesche Funktion F, deren zugehöriger Graph G dreiecksfrei ist, durch eine hinsichtlich der Readability optimale Formel p dargestellt werden kann, so dass p einer Kantenüberdeckung c von G durch Kantenmengen vollständiger bipartiter Teilgraphen entspricht. Hierbei ist die Anzahl, wie oft eine bestimmte Variable x in p vorkommt, gleich der Anzahl von vollständigen bipartiten Teilgraphen, welche von c benutzt werden und den Knoten x enthalten. - In Ihrem Manuskript bewiesen Golumbic et al. die Beziehung zwischen der Readability und der Problematik der Graphenüberdeckung für eine spezielle Folge von Graphen. In Abschnitt 2 beweisen wir als unser erstes Hauptresultat, dass die Argumente von Golumbic et al. noch für eine andere Folge von Graphen funktionieren. Darüber hinaus bearbeiten wir in Abschnitt 3 einen Spezialfall dieser Problematik, welcher Formeln einer eingeschränkten Struktur behandelt, dessen zugehörige Graphen dreiecksfrei sind.