Teoria Ramseya – dział matematyki, nazwany tak na cześć brytyjskiego matematyka i filozofa Franka Ramseya. Teoria ta bada warunki, pod którymi porządek musi się pojawić. Zajmuje się poszukiwaniem regularności, które pojawiają się w przypadkowych nieuporządkowanych obiektach, jeśli te zwiększają się, ogólnych warunków istnienia pod-struktur z regularnymi własnościami[1].
Typowymi problemami tej teorii są odpowiedzi na pytania: „jak wiele elementów pewnej struktury musi wystąpić, aby zaszła poszczególna własność.” Z teorii tej wynika wniosek przypisywany Theodore’owi Motzkinowi: „zupełny nieporządek jest niemożliwy”[2].
Twierdzenie Van der Waerdena (1927) – Dla każdej danej dodatniej całkowitej liczby c oraz n, istnieje liczba V, taka że jeśli ciąg złożony z następujących po sobie V liczb jest pokolorowany na c różnych kolorów, wówczas ciąg ten musi zawierać podciąg o postępie arytmetycznym o długości n, taki, że jego elementy są tego samego koloru. Oznacza to, że kolorując kolejne liczby na pewną liczbę kolorów, przy pewnej (być może znacznej) długości ciągu uzyskamy pewien rodzaj regularności (nie ma „ucieczki w idealny chaos” przed tym specyficznym porządkiem, jeśli odpowiednio zwiększymy V).
Wyniki w teorii Ramseya mają zwykle dwie główne cechy:
Po pierwsze są niekonstruktywne: mogą wykazać, że pewna struktura istnieje, ale nie przedstawiają procesu, w jaki ta struktura mogłaby zostać odnaleziona (innego niż przeszukiwanie „brute force”). Przykład: zasada szufladkowa Dirichleta.
Po drugie, mimo że wyniki teorii Ramseya stwierdzają, że wystarczająco wielki obiekt musi koniecznie zawierać daną strukturę, to jednak często dowód tych wyników wymaga, by te obiekty były niezwykle wielkie – ograniczenia rosną wykładniczo, a nawet nierzadko tak szybko, jak funkcja Ackermanna. W wielu przypadkach ograniczenia te uzyskuje się z dowodów twierdzeń i nie jest wiadomo, czy mogą być znacząco poprawione. W innych przypadkach jest wiadomo, że jakiekolwiek istniejące ograniczenie musi być niezwykle wielkie, czasem nawet większe niż jakakolwiek funkcja pierwotnie rekurencyjna. Liczba Grahama, która jest jedną z największych liczb kiedykolwiek użytych w poważnym matematycznym dowodzie, jest górnym ograniczeniem problemu związanego z teorią Ramseya.
↑Hans Jürgen Prömel (2005). „Complete Disorder is Impossible: The Mathematical Work of Walter Deuber”. Combinatorics, Probability and Computing (Cambridge University Press) 14: 3–16.
