[MD-sorular] Karenin Dikdortgensiz Altkumeleri

[Firat Solgun]

Merhaba,

MD'nin ilk sayisinda 'Karenin Dikdortgensiz Altkumeleri' adli bir yazi
var. Sanirim bu listede daha once tartisilmadi.
En buyuk dikdortgensiz altkumenin eleman sayisi icin alt ve ust
sinirlar bulunabilir:

Ust sinir icin:
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.

Alt sinir icin:
Yeterince buyuk N icin, siyah noktalari sutunlara belli oranlarda
paylastirarak N^(4/3) buyuklugunde dikdortgensiz altkumeler
bulabiliriz. Bunun nasil yapilacagini yazmak biraz daha yer
kaplayacagi icin daha sonra yazmayi dusunuyorum.

Firat