Ramseyteori

Ramseyteori är ett ämnesområde inom matematiken som kan sägas studera hur ordning måste uppstå i strukturer om de är tillräckligt stora. Området är uppkallat efter den brittiska matematikern Frank P. Ramsey.

Viktiga resultat

Ramseys sats

En 2-färgning av K₅ utan en enfärgad K₃.

Anta att vi har fått en lista på 6 personer, vilka som helst. Då visar sig att på den listan måste det finnas en grupp av tre personer som alla känner varandra, eller en grupp av 3 personer där ingen känner någon av de andra. (Eller båda två.)

Denna sats bevisas rigoröst, om man antar att "A känner B" är samma sak som att "B känner A" inom Ramseyteorin och kan sägas vara en startpunkt för teorin. I satsens typiska matematiska formulering handlar den om färgläggning av kanterna på en graf.

Om vi har en fullständig graf med 6 noder och färgar alla kanter med någon av två färger, t.ex. blå och röd, måste det finns en delgraf med tre noder där kanterna i delgrafen alla har samma färg. (Att en graf är fullständig betyder helt enkelt att varje par av noder är sammankopplade med en kant.) Vi säger att en delgraf är enfärgad om alla kanter i den har samma färg.

Om man har en fullständig graf med fler än 6 noder och färglägger den med två färger kan man då garantera att det finns en enfärgad delgraf med fler än 3 noder? Det visar sig att man har en graf med 18 noder finns det en enfärgad delgraf med 4 noder.

Man kan visa att för varje naturligt tal k finns det ett tal n så att alla grafer med n noder vars kanter färgas med två färgar måste ha en enfärgad delgraf av storlek k, Ramseys sats.

van der Waerdens sats

Det finns också viktiga resultat inom Ramseyteorin som inte handlar om grafer. Ett av dem är van der Waerdens sats som säger för alla naturliga tal c och n finns det ett heltal V så att om V på varandra följande heltal färgas med en av c färger kommer det alltid finnas en aritmetisk talföljd av längd n som är enfärgad.

Referenser

• Diestel, Reinhard (2005). Graph Theory. Springer Verlag. sid. 251ff