Partitiestellingen

Het ladenprincipe, ook wel bekend onder de naam duivenhokprincipe, zegt in zijn simpelste vorm dat als een voldoende aantal objecten verdeeld wordt over niet te veel laden, er minstens ´e´en lade is die veel van deze objecten bevat. In 1930 ontdekte Frank P. Ramsey [Ramsey] een bijzondere uitbreiding van dit principe die onder andere zegt dat als we de verzameling van takken van een oneindige volledige graaf in twee klassen verdelen, er een oneindige volledige deelgraaf is waarvan alle takken tot dezelfde klasse behoren. Het principe toont aan dat vanaf een bepaalde omvang willekeurige structuren noodzakelijkerwijs regelmatige deelstructuren moeten bevatten. Dit verslag geeft de resultaten van het onderzoek dat gedaan is naar de Stelling van Ramsey en de mogelijke uitbreidingen hiervan. Veel resultaten komen tot stand door het nemen van een partitie van een verzameling en vervolgens op een handige manier de verschillende objecten van de verzameling in de juiste klassen van de...Show moreHet ladenprincipe, ook wel bekend onder de naam duivenhokprincipe, zegt in zijn simpelste vorm dat als een voldoende aantal objecten verdeeld wordt over niet te veel laden, er minstens ´e´en lade is die veel van deze objecten bevat. In 1930 ontdekte Frank P. Ramsey [Ramsey] een bijzondere uitbreiding van dit principe die onder andere zegt dat als we de verzameling van takken van een oneindige volledige graaf in twee klassen verdelen, er een oneindige volledige deelgraaf is waarvan alle takken tot dezelfde klasse behoren. Het principe toont aan dat vanaf een bepaalde omvang willekeurige structuren noodzakelijkerwijs regelmatige deelstructuren moeten bevatten. Dit verslag geeft de resultaten van het onderzoek dat gedaan is naar de Stelling van Ramsey en de mogelijke uitbreidingen hiervan. Veel resultaten komen tot stand door het nemen van een partitie van een verzameling en vervolgens op een handige manier de verschillende objecten van de verzameling in de juiste klassen van de partitie te plaatsen. We spreken vanwege deze reden vaak over partitierelaties en noemen de stellingen die we behandelen partitiestellingen. Hoofdstuk 1 is een inleiding in partitierelaties en vormt de basis voor alles wat verder volgt. Het hoofdstuk is met name belangrijk omdat het partitiesymbool hierin ge¨ıntroduceerd wordt. Door gebruik te maken van dit symbool kunnen partitierelaties op een korte en duidelijke manier weergegeven worden. Hoofdstuk 2 behandelt de Stelling van Ramsey en geeft een beperkte uitbreiding van deze stelling. De Stelling van Erd˝os en Rado wordt in hoofdstuk 3 behandeld. Deze stelling is een uitbreiding van de stelling van Ramsey naar het overaftelbare geval. Het hoofdstuk kan het beste gelezen worden na hoofdstuk 2 aangezien het een logisch vervolg hierop is. Er wordt aangenomen dat de lezer bekend is met de basisprincipes van de verzamelingenleer. Een korte herhaling van de belangrijkste begrippen en notatie, wordt gegeven in de bijlage. Een andere belangrijke aanname die we maken is het keuzeaxioma; dat wil zeggen, we gebruiken het axiomastelsel van Zermelo–Fraenkel altijd samen met het keuzeaxioma. De belangrijkste bron waar gebruik van is gemaakt tijdens het onderzoek, is [Erd˝os et al.]. Voor een ieder die meer wil weten over het onderwerp is dit boek aan te raden.Show less

Leiden University Student Repository

Documents

In Collections

Partitiestellingen