Detailansicht
Die Ramsey-Theorie und ihre Anwendungen in der Graphentheorie
Franziska Schuster
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Lehramt Sek (AB) Unterrichtsfach Biologie und Umweltbildung Unterrichtsfach Mathematik
Betreuer*in
Markus Fulmek
DOI
10.25365/thesis.79008
URN
urn:nbn:at:at-ubw:1-23600.61875.470241-5
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Diese Arbeit behandelt zentrale Konzepte der Graphentheorie und der Ramsey-Theorie, zwei bedeutende Teilgebiete der diskreten Mathematik. Nach einer Einführung in grundlegende Begriffe wie Knoten, Kanten und Wege werden Verfahren zur Bestimmung kürzester Verbindungen vorgestellt, um erste strukturierte Abläufe in Graphen zu verdeutlichen. Weiters erfolgt eine Darstellung verschiedener Graphklassen, darunter bipartite und vollständige Graphen, die grundlegende Konzepte der Graphentheorie veranschaulichen. Ergänzend dazu werden klassische Strukturen sowie graphentheoretische Eigenschaften analysiert, die in engem Zusammenhang mit strukturellen Fragestellungen stehen. Darauf aufbauend wird die Ramsey-Theorie als Theorie struktureller Unvermeidbarkeit eingeführt. Ihr Grundprinzip sowie ihre historische Entwicklung werden eingehend erläutert, bevor zentrale Aussagen, insbesondere der Satz von Ramsey, anhand anschaulicher Beispiele veranschaulicht werden. Zudem werden zwei weitere Sätze vorgestellt, die eng mit dem Ramsey-Satz verwandt sind. Im Mittelpunkt der Anwendung der Ramsey-Theorie in der Graphentheorie steht das Auftreten monochromatischer Teilgraphen in gefärbten vollständigen Graphen. Darüber hinaus wird untersucht, wie sich dieses Prinzip auf bipartite Strukturen sowie auf Färbungen mit mehr als zwei Farben übertragen lässt. Abschließend wird die Bedeutung von Zufallsgraphen im Kontext ramsey-theoretischer Fragestellungen aufgezeigt. Durch die Verbindung beider Theorien entsteht ein vertieftes Verständnis für die Wechselwirkungen zwischen Struktur, Größe und Färbung in Graphen. Dabei wird deutlich, wie sich scheinbare Unordnung mathematisch beschreiben lässt und unter welchen Bedingungen Ordnung unausweichlich wird. Abschließend werden aktuelle Forschungsrichtungen und offene Probleme thematisiert, da viele Fragestellungen der Ramsey-Theorie bislang ungelöst sind und nur für wenige Spezialfälle exakte Ramsey-Zahlen bekannt sind. Dies unterstreicht die Relevanz weiterer theoretischer und algorithmischer Forschung in diesem spannenden Gebiet.
Abstract
(Englisch)
This thesis discusses fundamental concepts of graph theory and Ramsey theory, two significant branches of discrete mathematics. It begins with an introduction to key terms such as nodes, edges, and paths, followed by methods for determining shortest connections to illustrate initial structured processes in graphs. Furthermore, various graph classes are presented, including bipartite and complete graphs, which illustrate fundamental concepts of graph theory. In addition, classical structures and graph-theoretical properties closely linked to structural questions are analyzed. Building on this, Ramsey’s theory is introduced as a theory of structural inevitability. Its core principle and historical development are thoroughly explained, followed by central results, particularly Ramsey’s theorem, illustrated through concrete examples. Furthermore, two additional theorems closely related to Ramsey’s theorem are discussed. The main focus of applying Ramsey’s theory in graph theory lies in the occurrence of monochromatic subgraphs in coloured complete graphs. This principle is then extended to bipartite structures and colourings involving more than two colours. The role of random graphs in the context of Ramsey-theoretical considerations is also examined. By combining both theories, a deeper understanding emerges of the interplay between structure, size, and colouring in graphs. It is shown how apparent disorder can be described mathematically and under which conditions order becomes unavoidable. Finally, current research directions and open problems are addressed, as many questions in Ramsey theory remain unsolved and exact Ramsey numbers are only known for a few specific cases. This highlights the relevance of continued theoretical and algorithmic research in this compelling field.
Schlagwörter
Schlagwörter
(Deutsch)
Ramsey-Theorie Graphentheorie
Autor*innen
Franziska Schuster
Haupttitel (Deutsch)
Die Ramsey-Theorie und ihre Anwendungen in der Graphentheorie
Paralleltitel (Englisch)
The Ramsey theory and its applications in graph theory
Publikationsjahr
2025
Umfangsangabe
viii, 89 Seiten : Illustrationen
Sprache
Deutsch
Beurteiler*in
Markus Fulmek
Klassifikation
31 Mathematik > 31.12 Kombinatorik. Graphentheorie
AC Nummer
AC17609577
Utheses ID
77008
Studienkennzahl
UA | 199 | 502 | 520 | 02