Teoria Ramseya

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].

Kluczowe twierdzenia

Twierdzenie Ramseya (1930)
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).
Twierdzenie Halesa–Jewitta (1963)
Twierdzenia Schura (1916)
Twierdzenie Rado (1943)

Wyniki

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.

Zobacz też

Bartel Leendert van der Waerden
kombinatoryka

Przypisy

↑ Eric W.E.W. Weisstein Eric W.E.W., Ramsey Theory, [w:] MathWorld, Wolfram Research [dostęp 2020-12-13] (ang.).
↑ 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.

Linki zewnętrzne

Największa liczba na świecie Portal popularnonaukowy miesięcznika „Delta” [dostęp 2021-09-01].

Działy matematyki dyskretnej

kombinatoryka	teoria Ramseya
teoria grafów	algebraiczna geometryczna spektralna topologiczna
inne	geometria dyskretna geometria kombinatoryczna geometria skończona kryptologia logika matematyczna teoria gier działy algebry abstrakcyjnej działy algorytmiki działy teorii liczb

Działy matematyki

działy
ogólne

według trudności	matematyka elementarna matematyka wyższa
według celu	matematyka czysta matematyka stosowana
inne	matematyka doświadczalna matematyka parakonsystentna supermatematyka

działy
czyste

algebra	elementarna liniowa i wieloliniowa abstrakcyjna algebra przemienna algebra lokalna teoria Galois różniczkowa teoria Galois teoria grup geometryczna teoria grup teoria Liego homologiczna różniczkowa uniwersalna teoria reprezentacji
analiza matematyczna	analiza algebraiczna analiza funkcjonalna teoria spektralna analiza geometryczna analiza globalna analiza harmoniczna analiza mikrolokalna analiza na rozmaitościach analiza niestandardowa analiza numeryczna nomografia analiza p-adyczna analiza rzeczywista analiza wektorowa analiza wielowymiarowa analiza wypukła analiza zespolona rachunek różniczkowy i całkowy rachunek wariacyjny teoria dystrybucji teoria miary teoria potencjału
arytmetyka	elementarna teoretyczna lub wyższa, in. teoria liczb algebraiczna algorytmiczna analityczna elementarna geometryczna teoria sit
geometria	absolutna afiniczna algebraiczna analityczna arytmetyczna diofantyczna dyskretna euklidesowa planimetria stereometria fraktalna inwersyjna kombinatoryczna konforemna metryczna nieeuklidesowa eliptyczna hiperboliczna sferyczna nieprzemienna obliczeniowa różniczkowa symplektyczna rzutowa skończona syntetyczna tropikalna uporządkowania wykreślna zespolona trygonometria sferyczna
matematyka dyskretna	kombinatoryka teoria Ramseya teoria grafów algebraiczna geometryczna spektralna topologiczna
podstawy	logika matematyczna algebraiczna mereologia rachunek zdań teoria dowodu teoria modeli teoria rekursji teoria typów metamatematyka metalogika teoria kategorii teoria mnogości opisowa arytmetyka liczb kardynalnych arytmetyka liczb porządkowych teoria PCF teoria obliczeń teoria obliczalności teoria złożoności
teoria układów dynamicznych	teoria chaosu teoria katastrof teoria ergodyczna
topologia	algebraiczna teoria homotopii geometryczna mnogościowa ogólna różniczkowa teoria Morse’a teoria położenia teoria węzłów teoria warkoczy teoria wymiaru
pozostałe	K-teoria probabilistyka rachunek różnicowy teoria osobliwości teoria porządku teoria punktu stałego

działy
stosowane

nauki przyrodnicze	biomatematyka chemia matematyczna fizyka matematyczna
nauki społeczne	ekonomia matematyczna lingwistyka matematyczna matematyka finansowa matematyka ubezpieczeniowa psychologia matematyczna socjologia matematyczna teoria głosowań
nauki techniczne	kryptologia teoria informacji teoria kolejek teoria sterowania
statystyka matematyczna	rachunek wyrównawczy statystyka nieparametryczna teoria estymacji
inne	teoria gier teoria decyzji