In matematik ve özellikle de kombinatorik , Ramsey teorisi adını, Frank Ramsey , formun cevap sorulara genellikle girişimleri: "doğrulanır belirli bir özellik için kaç belli yapının unsurları göz önünde bulundurulmalıdır? "
Bu formun bir sonucunun ilk örneği, 1834'te Dirichlet tarafından dile getirilen çekmece prensibidir .
Örneğin, n tane çorabın m çekmecede saklandığını varsayalım . En az iki çorap içeren en az bir çekmece olduğundan emin olabileceğimiz n tamsayısının bir değeri var mı ? Çekmece prensibinin verdiği cevap, n > m olduğu anda durumun böyle olduğudur . Ramsey teoremi bu prensibi genelleştirir.
Ramsey'in teorisindeki tipik bir sonuç, daha sonra parçalara ayrılan belirli bir matematiksel yapının dikkate alınmasıyla başlar. Parçalardan en az birinin bazı özelliklere sahip olmasını sağlamak için orijinal yapı ne kadar büyük olmalıdır?
Örneğin, n sırasının tam bir grafiğini , yani bir kenarla birbirine köşeye bağlanmış n köşeye sahip olduğunu düşünün (3. dereceden tam bir grafiğe üçgen denir). Şimdi her bir kenarı kırmızı veya maviye boyayalım. Ne miktar n o sağlamak amacıyla sahip olmalıdır olursa olsun, en az bir mavi üçgen veya bir kırmızı üçgen varlığını boyama seçilmiş? Cevap 6 olarak gösterilebilir . Bu sonuç şu şekilde yeniden ifade edilebilir: En az altı kişinin katıldığı bir partide, birbirini tanıyan en az üç kişi veya birbirine yabancı en az üç kişi vardır.
Ramsey teorisinin sonuçları arasında, Ramsey teoreminden başlayarak aşağıdaki örnekleri ayırt edebiliriz.
Derecesi, sonlu dizisi için (gösterir Ramsey teoreminin, özel bir durumu olan , n 1 , ..., n- c ) bir tamsayı, bir tam sayı vardır R öyle ki, kenarları K R ( grafiği tamamlamak arasında sipariş R ) ile renkli c renkleri, o zaman bir renk vardır i öyle ki K R için tam bir alt grafiğini içermektedir n ı renk ve tek renkli i .
Yukarıdaki özel durum c = 2 ve n 1 = n 2 = 3'e karşılık gelir.
Ramsey teorisinin diğer ana teoremleri şunlardır:
Teoremi Paris ve Harrington (in) gösterir Ramsey bir varyantı teoremi bir ifadedir bitmiş undecidable gelen Peano aksiyomları . Tarihsel olarak, bu 1977 teoremi (bir “doğru” aritmetik ilk örnek teşkil yani içinde şifreleyen bir “Gödelian” türetilmiş olan) undecidable deyimi Peano aritmetik sonra, 46 yıl teoremi d 'eksiklik Gödel arasında . O zamandan beri, Goodstein teoremi gibi başkalarını tanıyoruz . Bu sonuç, Handbook of Mathematical Logic'e , ardından yayın sürecine dahil edilecek kadar önemli görüldü ve disiplinin bir sentezi olması amaçlandı.
Not: [ A ] n, tüm alt-gruplar boyutta n bir A .
Teoremi - Let A aşağıdaki bir sayılabilir sonsuz grubu ve n, bir tam sayı . Herhangi biri için boyama [ait A ] n, bir renk sonlu sayısına göre, burada bir sonsuz alt guruplarında B arasında bir şekilde [ B ] , n , tek renkli bir.
Her sonsuz küme sayılabilir bir parça içerdiğinden, A'nın sonsuz olduğunu varsaymakla tatmin olabiliriz .
Teoremin sonsuz versiyonu, sonlu versiyonu ifade eder.
Bu teorem, özellikle yinelemeli bölümler hakkında çeşitli genellemeler biliyor.
Aynı zamanda (çok!) Büyük bir kardinal olan " Ramsey'in kardinali " nosyonunun da kökenindedir . Bir sonsuz ana κ ( bir dizi olarak görülmektedir ) herhangi ise “Ramsey” olduğu söylenir bölme iki sınıfa k sonlu parça setinin, K bir parçası vardır A kardinal k ve “homojen”, c Yani, tüm n'ler için [ A ] n iki sınıftan birine dahil edilecek şekilde.
Ramsey teorisi teorik bilgisayar biliminde , özellikle dağıtılmış hesaplama teorisinde kullanılır .