Ramsey-teori
Ramsey-teori, oppkalt etter Frank Plumpton Ramsey er en gren av kombinatorikk. Problemer i Ramsey-teori er av typen «hvor mange elementer i en bestemt struktur behøves for at en bestemt egenskap skal være oppfylt?»
Et enkelt eksempel er skuffeprinsippet: Anta at man har n skuffer, samt m kuler som skal plasseres i dem. Hvor stor må m minst være for at man skal være sikker på at det finnes en skuff med minst to kuler. Svaret er åpenbart at m ≥ n+1.
Et annet eksempel som ofte brukes for å illustrere Ramsey-teori er det følgende. Anta at minst seks personer er til stede i et selskap. Da vil det alltid enten være tre personer blant disse seks slik at alle tre kjenner hverandre fra før, eller så vil det være tre personer slik at ingen av de tre kjenner noen av de to andre fra før. For en generalisering av dette problemet, se Ramseys teorem.
Noen andre viktige teoremer innen Ramsey-teori er
- Van der Waerdens teorem: For alle naturlige tall n og k, finnes det et naturlig tall N slik at hvis man fargelegger alle heltallene fra 1 til N med k farger, vil det alltid finnes en aritmetisk følge der alle tallene er fargelagt med den samme fargen.
- Hales-Jewett-teoremet: For alle naturlige tall n og k, finnes det et naturlig tall N slik at hvis alle cellene i en N-dimensjonal n×n×n×…×n-kube blir fargelagt med k farger, vil det alltid finnes en rad, kolonne etc. av lengde n slik at alle cellene har samme farger. Hales-Jewett-teoremet impliserer Van der Waerdens teorem.
- Schurs teorem: For ethvert naturlig tall k, finnes et naturlig tall N slik at hvis heltallene fra 1 til N fargelegges med k farger, må det finnes et par av heltall x, y slik at x, y og x+y alle har samme farge. Det finnes mange generaliseringer av dette teoremet, som Rados teorem, Rado-Folkman-Sanders-teoremet, Hindmans teorem og Milliken-Taylor-teoremet.
Resultater i Ramsey-teori har ofte to typiske særtrekk. For det første har de ofte ikke-konstruktive bevis; det vil si at man beviser at en bestemt struktur eksister, men gir ingen oppskrift for å finne en slik struktur. For det andre, når teoremer i Ramsey-teori sier at et tilstrekkelig stort objekt nødvendigvis må ha en viss struktur, legges det ofte i begrepet «tilstrekkelig stort» at størrelsen på objektet må vokse eksponentielt med størrelsen på den strukturen som ønskes, eller til og med enda raskere, som for eksempel Ackermann-funksjonen.