Ramsey-teori for grafer
Forfattere
Pedersen, Mikkel Larsen ; Juel, Anders Lindberg
Semester
4. semester
Uddannelse
Udgivelsesår
2008
Abstract
Dette speciale undersøger Ramsey-teori i grafteori, altså hvornår bestemte mønstre uundgåeligt opstår i store netværk af punkter og kanter (grafer). Første del introducerer de klassiske Ramsey-tal—de mindste størrelser, der garanterer en ønsket delstruktur—og forklarer, hvordan litteraturen opnår grænser (nedre og øvre) og eksakte værdier med forskellige bevisteknikker. Anden del behandler generaliserede Ramsey-tal for bestemte grafklasser og fastslår grænser og eksakte værdier for veje (enkle kæder), træer (forgrenede strukturer), vifte-grafer, bog-grafer og kombinationer heraf. Specialet afsluttes med et resultat i Ramsey-teori om, hvor mange punktdisjunkte delgrafer (delgrafer, der ikke deler punkter) man kan garantere.
This thesis explores Ramsey theory in graph theory—the study of when certain patterns must appear in large networks of points and edges (graphs). Part I introduces the classical Ramsey numbers—the smallest sizes that guarantee a desired substructure—and explains how the literature obtains bounds (lower and upper) and exact values using different proof techniques. Part II examines generalized Ramsey numbers for specific graph families, establishing bounds and exact values for paths (simple chains), trees (branching structures), fan graphs, book graphs, and combinations of these. The thesis concludes with a Ramsey-theoretic result about how many vertex-disjoint subgraphs (subgraphs that share no vertices) can be guaranteed.
[Dette resumé er genereret ved hjælp af AI]
Emneord