[MD-sorular] Karenin Dikdortgensiz Altkumeleri

Firat Solgun firat.solgun at gmail.com
25 Haz 2009 Per 11:26:40 EEST


Merhaba,

Dun bu konuda bir mesaj attim ama sanirim listeye ulasmadi.

MD'nin ilk sayisinda 'Karenin Dikdortgensiz Altkumeleri'
<http://matematikdunyasi.org/arsiv/PDF/03-I-62-62-DikdortgensizKar.pdf>adli
bir yazi var. Sanirim bu konu bu listede daha once tartisilmadi. Karenin bir
kenarindaki nokta sayisina N dersek, yazida N = 2,3,4,5,6,7 icin
dikdortgensiz en buyuk altkume ornekleri veriliyor. Yazinin son paragrafinda
dikdortgensiz en buyuk altkumenin eleman sayisinin N'ye bagli olarak nasil
davrandigi soruluyor. Bu sayi icin bir ust sinirin N^(3/2) oldugunu
dusunuyorum:

Karenin satir ve sutunlarini 1'den N'ye numaralandiralim. Her i numarali
sutun icin, o sutundaki siyah noktalarin satir numaralarini iceren A(i)
kumeleri olusturalim. Ornegin 1.sutundaki siyah noktalar 2., 3. ve 5.
satirlardaysa A(1) = {2,3,5} olacak. Karenin altkumelerinde dikdortgen
olmamasi icin yeterli ve gerekli kosul, farkli i ve j sutunlari icin A(i)
kumesinden elde edilecek ikililerin A(j) kumesinden elde edilecek
ikililerden farkli olmasidir. Simdi k(i) i numarali sutundaki siyah
noktalarin sayisi olacak sekilde bir k dizisi tanimlayalim ve (m,2) m
elemanli bir kumeden secilebilecek toplam ikili sayisi olsun. Bu durumda,
dikdortgensiz bir kare icin (k(1),2) + (k(2),2) + ... + (k(N),2) <= (N,2)
esitsizligi gecerlidir. Karedeki toplam siyah nokta sayisina S diyelim, S =
k(1) + k(2) + ... + k(N). Herhangi bir S icin, yukaridaki esitsizligin sol
tarafi her i icin k(i) = S/N oldugu zaman en kucuk olur ve bu durumda S <= N
x karekok(N-3/4) + N/2 esitsizligi elde edilir. Buradan en buyuk altkumenin
toplam noktalara oraninin sifira yakinsadigi da cikar.

Ayrica yeterince buyuk N icin, siyah noktalari sutunlara belli oranlarda
paylastirarak N^(4/3) buyuklugunde dikdortgensiz altkumeler bulabiliriz, bu
da bize yeterince buyuk N icin, dikdortgensiz en buyuk alt kumedeki eleman
sayisina bir alt sinir verir. Dunku mesajimda bunun nasil yapilacagini daha
sonra yazacagimi soylemistim. Ancak kullandigim yontem biraz zorlama bir
yontem oldugu icin kanit okunmasi zor bir hal aldi, daha sonra gerekirse
listeye yollayabilirim. Ama yazinin MD'de yayinlanmasindan bu yana
N^(4/3)'ten daha buyuk bir alt sinir oneren oldu mu merak ediyorum? Alt
siniri daha yukari cekebilir misiniz?

Firat
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20090625/3f3faca0/attachment-0001.htm 


MD-sorular mesaj listesiyle ilgili daha fazla bilgi