[MD-sorular] lineer uzayda bir kombinatoryal teorem

[Metin Odun]

Aga sağol. De Bruijn-Erdös teoremi (
http://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem) geliyor
haftaya falan. Bakalım, hayırlısı. Da, sonlular için yapacağız. Bize Seçim
Beliti falan anlatmadılar! Dergilerden de öğrenilemiyor hemencecik...

Hislerime tecüman oldun. Hata yaptığımı hissettiğim ne kadar yer varsa
hepsine parmak basmışsın. "İki nokta" olayı çok yerinde bir tespit.
Tümevarımla aynı uzunluk ve zorluk... Tam ben de öyle düşünmüştüm. Aslında
topu taça atmış oluyorum. Şov yapıp nat ku iplayz nat pi is locikıllıy
ikuvalent to ku impliez pi sevdasına kısır döngüye girdim.

Kaçamak güreştim bu soruda. Kabul ediyorum. Tümevarım kanıtlarını kırmızı
kar yağınca yapacağım çünkü halkalardan bi buçuk ton ödevim var...

Çok sağol hacı.

"Bir soruyu anlamak, onu çözmek demektir." Metin Odun özlü sözü.

Metin

18 Ekim 2009 19:28 tarihinde tibet efendi <tibetefendi at yahoo.com> yazdı:

> Bu matematigin hangi dali oluyor? Cok eglenceliymis. Bunun adi kombinatorik
> geometri degil mi? Keske ben de alabilsem böyle bir ders dedirtti.
>
> Bence bir yerde hata yapiyorsun haci. Daha dogrusu hata degil de sicrama
> yapiyorsun. Ama önce bir seye aciklik getirelim. (kirmizi bölgede)
>
> Önerdigin kanitta demissin ki:"U bir pür YLU ise (LU olmayan bir YLU) (b_j
> üzerinden) Toplam [vj(v_j-1)]<v(v-1) olur zira U'da birleşmeyen nokta var."
>
> "Pür YLU'larda birlesmeyen nokta var" demissin.
> Bu ne anlama geliyor?
> "Pür YLU'larda havada asili, hic bir noktayla baglantisi olmayan bir nokta
> var"
> anlaminda söylüyorsan yanlis.
> Ama sanirim "Pür YLU'larda üzerlerinden ortak bir dogru gecmeyen iki nokta
> vardir" anlaminda söylüyorsun ki bu dogru.
>
> yani "pür YLU" aksiyomlari söyle olmali:
>
> pürYLU1) her dogru en az iki nokta kapsar.
> pürYLU2) Her iki noktadan en cok bir dogru gecer ve öyle bir nokta ikilisi
> vardir ki üzerlerinden gecen bir dogru yoktur.
>
> Simdi sen önerdigin kisa kanitta diyorsun ki:
> "U bir pür YLU ise (b_j üzerinden) Toplam [vj(v_j-1)]<v(v-1) olur zira
> U'da birleşmeyen iki nokta var."
>
> "iki" lafini ben ekledim. Sebebi, yukaridaki kirmizi bölge.
>
> Bunun kanitini nasil yapiyorsun? Bunun kaniti tümevarimla yapilmali bence.
> Kaldi ki bence verdigin uzun kanitin (=>) kismindaki esitlik de da
> tümevarimla kanitlanmali.
>
> Simdi senin önerdigin kanittaki esitsizligin tümevarimla kaniti, elindeki
> uzun dedigin kanita esdeger bir kanit olmali. Ve asagi yukari ayni uzunlukta
> ve zorlukta olmali.
>
> Ha bir de yazdigin tümevarim kaniti bana yanlis göründü. Yazmissin ki:
> "(<=) v üzerinden tümevarımla U'nun bir LU olduğu kanıtlanıyor. Şöyle. v=1,
> 2, 3 durumlarında sorun yok. v>=4 farzediliyor. Eşitisizliğin v-1 noktalı
> bir YLU için doğru iken v noktalı bir YLU için doğruluğu kabul ediliyor. v-1
> noktalı N'=N\{N_i} uzayında eşitsizliğin doğru olduğu ise U' ve U
> uzaylarında toplamların N'yi içeren ve içermeyen doğrulardan faydalanılarak
> yazılmasıyla kolayca elde ediliyor."
>
> Benim önerim su sekilde:
> (<=) v üzerinden tümevarımla kanıtlayalim.
> Şöyle:
> v=1 icin iddia dogru.
> v-1 noktalı bir YLU için,"*esitsizlikten, bu YLU'nun bir LU oldugu
> sonucunun ciktigini"* kabul edelim. (Bu, tümevarim varsayimimiz)
> i elemanidir {1,...,v} icin
> D_i:=D\{d_j EURO D : d_j'nin eleman sayisi 2 ve N_i elemanidir d_j}
> tanimini yapalim.
> Simdi v elemanli bir N icin (N,D) yari lineer uzayinin esitsizligi
> gerceklestirdigini kabul edelim. Buradan hareketle ({N\{N_i}, D_i) yari
> lineer uzayinda esitsizligin dogru oldugunu kanitlayalim. Tümevarim
> varsayimimiz bu noktada bize, ({N\{N_i}, D_i) yari linner uzayinin bir
> lineer uzay oldugunu söylüyor. Geriye, buradan hareketle (N,D)'nin de bir LU
> oldugunu göstermek kaliyor.
>
> (Tümevarimi 4'ten baslatmak icin bir sebep göremiyorum.)
>
> Biraz karisik görünüyor ama bu tür kanitlarda tümevarimla kanitlamaya
> calistigimiz iddianin ne oldugunu, tümevarim baslangicini ve tümevarim
> varsayimimizi dogru düzgün yazarsak isler karismadan halloluyor.
>
> tibet
>
> --- On *Sun, 10/18/09, Metin Odun <metamaths at gmail.com>* wrote:
>
>
> From: Metin Odun <metamaths at gmail.com>
> Subject: [MD-sorular] lineer uzayda bir kombinatoryal teorem
> To: md-sorular at matematikdunyasi.org
> Date: Sunday, October 18, 2009, 6:13 AM
>
>
> Kanıtı anladım da uzun biraz. Daha kısası var, hatta kanıtın içinde kendini
> belli ediyor bu kısalık. Da bu kısalıktan emin olamıyorum... Sorum da bu,
> kısalıkta haklı mıyım?
> *
> Bilenler alttaki çizgiden sonrasını okuyabilir.
>
> Biraz ön bilgi.* N noktalar kümesi, D doğrular kümesi olsun. U(N, D)'ye
> bir uzay diyelim. d_j, D'nin elemanı, yani bir doğru. v_j, d_j doğrusunun
> nokta sayısı. b=|D|, yani uzayın doğru sayısı. v=|N|, yani uzaydaki nokta
> sayısı.
>
> *Tanım. *Aşağıdaki aksiyomları sağlayan uzaya bir *yaklaşık lineer uzay*denir. (
> *YLU*)
>
> YL1. Her doğru en az iki nokta kapsar.
> YL2. Farklı iki noktadan en çok bir doğru geçer (Hiç geçmese de olur.)
>
> *Tanım.* Yukarıdaki tanımda YL2 aksiyomundaki "en çok" yerine "tam (bir ve
> yalnız bir)" alarak elde edilen uzaya bir lineer uzay (*LU*) diyelim.
> (Linner uzayda boşta nokta kalmaz yani. Bu lineer uzay vektör uzayı olmak
> zorunda değil, geometrideki lineer uzay bu.)
>
> --------------
>
> *Teorem.* U, sonlu bir *YLU*.
>
> U, LU <=> (b_j üzerinden) Toplam [vj(v_j-1)]>= v(v-1)
>
> Kanıtın sağdan sola kısmı uzun. Tüm kanıtın ana hatlarını aktarayım.
>
> (=>) Fazlası doğru, eşitlik var. Şuradan çıkıyor: ToplamC(v_j, 2)=C(v,2),
> çünkü lineer uzayda birleşmeyen nokta yok. (İki ile çarpmak kalıyor
> sadece...)
>
> (<=) v üzerinden tümevarımla U'nun bir LU olduğu kanıtlanıyor. Şöyle. v=1,
> 2, 3 durumlarında sorun yok. v>=4 farzediliyor. Eşitisizliğin v-1 noktalı
> bir YLU için doğru iken v noktalı bir YLU için doğruluğu kabul ediliyor. v-1
> noktalı N'=N\{N_i} uzayında eşitsizliğin doğru olduğu ise U' ve U
> uzaylarında toplamların N'yi içeren ve içermeyen doğrulardan faydalanılarak
> yazılmasıyla kolayca elde ediliyor.
>
> Hatta buradan eşitlik sonucu çıkıyor! Yani,
>
> U, sonlu bir *YLU*. U, LU <=> (b_j üzerinden) Toplam [vj(v_j-1)]= v(v-1)
>
> oluyor. Zira U, LU iken eşitlik vardı. Eştisizlik varken de U, LU oluyor.
> Demek ki sağdan sola geçerken eşitsizlik varken eşitlik oluyor.
>
> *Kısalık olayı*... U bir pür YLU ise (LU olmayan bir YLU) (b_j üzerinden)
> Toplam [vj(v_j-1)]<v(v-1) olur zira U'da birleşmeyen nokta var. Bunun karşıt
> değili de ilk teoremin sağdan sola geçişidir zaten! Bu kadar kısa. Madem
> ToplamC(v_j, 2)=C(v,2) derken "çünkü lineer uzay" diyor kanıtta, lineer uzay
> değilse de ToplamC(v_j, 2)<C(v,2) derim, ToplamC(v_j, 2)>C(v,2) olacak hali
> yok ya! Ama bunu da göremiyorum. Niye ToplamC(v_j, 2)>C(v,2) olmasın.
>
> Yine de çok hoş bir tümevarım kanıtı olsa da "Ne gerek var tümevarıma?"
> demek istiyorum.
>
> "Milii takım oleyyyy. Aaaaa, biliii takıım oleeeyvvv. Biviv takım oley,
> milli takım oleey. beşiktaşıım oleeeyyy. Beşiktaşım oley beşiktaşım oley.
> Yeeeteeeer, Yıldırıımm Demirören yeeeeteerrrr. Yönetim istifaaaaaaa, aaaaaa
> yönetim iiisstifaa, yönetim istiifaaaaa." "Hey! Dudup dup heeeyooooo heyy!
> Du-dup-dum!"
>
>
>
>
> -----Inline Attachment Follows-----
>
> _______________________________________________
> MD-sorular e-posta listesi
> sorular at matematikdunyasi.org
> http://lists.math.bilgi.edu.tr/cgi-bin/mailman/listinfo/md-sorular
>
>
>
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20091019/e7a0888b/attachment.htm