Rados teoremi (Ramsey teorisi) - Rados theorem (Ramsey theory) - Wikipedia

Rado teoremi dalından bir teoremdir matematik olarak bilinir Ramsey teorisi. Alman matematikçi adını almıştır. Richard Rado. Tezinde ispatlandı, Studien zur Kombinatorik.

Beyan

İzin Vermek bir doğrusal denklem sistemi olabilir, burada tamsayı girdileri olan bir matristir. Bu sistemin olduğu söyleniyor -düzenli her biri için 1, 2, 3, ... doğal sayılarının renklendirilmesi, sistemin tek renkli bir çözümü vardır. Bir sistem düzenli Öyleyse r-normal hepsi içinr ≥ 1.

Rado'nun teoremi, bir sistemin ancak ve ancak matris Bir tatmin eder sütun koşulu. İzin Vermek cben belirtmek ben-nci sütun Bir. Matris Bir bir bölüm olması koşuluyla sütun koşulunu karşılar C1, C2, ..., Cn sütun indekslerinin , sonra

  1. s1 = 0
  2. hepsi için ben ≥ 2, sben rasyonel olarak yazılabilir[1] doğrusal kombinasyonu cj'tümünde Ck ile k < ben. Bu şu demek sben doğrusal alt uzayında Qm dizi tarafından cj's.

Özel durumlar

Folkman teoremi Boş olmayan toplamları tek renkli olan keyfi olarak büyük tam sayı kümelerinin var olduğu ifadesi, denklem sisteminin düzenliliğiyle ilgili Rado teoreminin özel bir durumu olarak görülebilir.

nerede T kümenin her boş olmayan alt kümesi üzerinde aralıklar {1, 2, ..., x}.[2]

Rado teoreminin diğer özel durumları Schur teoremi ve Van der Waerden teoremi. İlkini kanıtlamak için Rado teoremini matrise uygulayın . Van der Waerden teoremi için m monokromatik aritmetik ilerlemenin uzunluğu olarak seçildiğinde, örneğin aşağıdaki matris düşünülebilir:

Hesaplanabilirlik

Bir doğrusal denklem sistemi verildiğinde, bunun düzenli olup olmadığını hesaplamalı olarak nasıl kontrol edeceği önceden belirsizdir. Neyse ki, Radu teoremi, sonlu zamanda test edilebilir bir kriter sağlar. Renklendirmeleri (sonsuz sayıda doğal sayıdan oluşan) dikkate almak yerine, verilen matrisin sütun koşullarını karşılayıp karşılamadığı kontrol edilmelidir. Matris yalnızca sonlu sayıda sütundan oluştuğundan, bu özellik sonlu zamanda doğrulanabilir.

Ancak alt küme toplamı sorunu olabilir indirgenmiş gerekli bölümü hesaplama problemine C1, C2, ..., Cn Sütun sayısı: Bir girdi kümesi verildiğinde S alt küme toplamı problemi için aşağıdaki unsurları yazabiliriz: S 1 × şeklinde bir matriste |S|. Sonra unsurları S bölümdeki vektörlere karşılık gelir C1 sıfıra toplamı. Alt küme toplamı problemi NP tamamlandı. Bu nedenle, bir doğrusal denklem sisteminin düzenli olduğunu doğrulamak da NP-tam bir sorundur.

Referanslar

  1. ^ Modern grafik teorisi Béla Bollobás. 1. baskı 1998. ISBN  978-0-387-98488-9. Sayfa 204
  2. ^ Graham, Ronald L.; Rothschild, Bruce L.; Spencer, Joel H. (1980), "3.4 Sonlu Toplamlar ve Sonlu Birlikler (Folkman Teoremi)", Ramsey Teorisi, Wiley-Interscience, s. 65–69.