[MD-sorular] Ramsey Kurami'ndan bir soru

[Baris PAKSOY]

Ramsey kurami uzerine calisirken aklima takildi bu soru; fakat nasil
ispatlayabilecegime dair en ufak bir fikir gelistiremedim, sanirim once iyi
bir boyama metodu gelistirmek gerekiyor. Yardimci olabilirseniz cok
sevinirim.

n koseli Kn tam cizgesini* ele alalim. Bu cizgenin tum kenarlarini uc farkli
renkle boyayacagiz, oyle ki tek renkten olusan bir ucgen mevcut olmasin. Uc
kenarida farkli renklerden olusan bir ucgenin varliginin garanti olmasi
icin, n sayisi en az kac olabilir?
Ipucu : Ornegin uc renk kullandigimiz bir boyamada tum kenarlari ayni
renkten olusan bir ucgenin varliginin garanti edilebilmesi icin n en az 17
olabilir. Bu da R(3,3,3) Ramsey sayisidir. Dolayisiyla burada da cevabimiz
17den kucuk olmak zorundadir, ama boyle bir n olmayabilirde.

*Tam cizgeden kasit her kosenin diger butun koselerle arasinda bir kenar
oldugunu belirtir. Ornegin 5 koseli bir tam cizge 10 kenar icermek
zorundadir.

-- 
Adres   : Istanbul Erkek Lisesi
             Turkocagi Caddesi No:4
             Eminonu/Istanbul/Türkiye

Telefon : +905445555926

Baris Paksoy
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20100121/b3670bbd/attachment.htm