Defective Ramsey numbers and defective cocolorings
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Boğaziçi Üniversitesi, FEN BİLİMLERİ ENSTİTÜSÜ, FEN BİLİMLERİ ENSTİTÜSÜ, Türkiye
Tezin Onay Tarihi: 2012
Tezin Dili: İngilizce
Öğrenci: AHU AKDEMİR
Danışman: TINAZ EKİM
Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
Özet:Ramsey sayısı, R(a, b) herhangi n kişi arasında her zaman birbirini tanıyan a kişi ya da birbirini tanımayan b kişi olmasını sağlayacak en küçük pozitif n tam sayısını vermektedir. Küçük a ve b değerleri için Ramsey sayıları tam olarak bilinmektedir ve bilinmeyen Ramsey sayıları için alt ve üst sınırlar hesaplanmıştır. Bir Ramsey sayısının alt ve üst sınırları, bu Ramsey sayısının alabileceği sırasıyla en küçük ve büyük değerleri ifade etmektedir. Bu çalışmada Ramsey sayılarının bir genelleştirmesi olan kusurlu Ramsey sayıları üzerinde çalıştık. Kusurlu Ramsey sayısı, Rk(a, b), n kişi arasında k istisnayla her zaman birbirini tanıyan a kişi ya da birbirini tanımayan b kişi olmasını sağlayacak en küçük pozitif n tam sayısını vermektedir. Bazı bilinmeyen Rk(a, b) değerleri için alt ve üst sınırları hesapladık ve bunların bazıları için alt sınırları geliştirdik. Ayrıca farklı çizge sınıflarında klasik ve kusurlu Ramsey sayılarını inceledik ve belirli bir çizge sınıfı için tam değerleri veya alt ve üst sınırları veren formüller geliştirdik. İkinci kısımda, çizgelerde tam boyama (cocoloring) problemi üzerinde çalıştık. Bir çizgenin düğümlerini klik ya da da bağımsız kümelere ayırarak her birine bir renk atanmasına problemine tam boyama problemi denir. Klik ya da bağımsız kümeler yerine k-yoğun (k-dense), bir düğümün en fazla k düğüm kaçırdığı klik, ve k-seyrek (k-sparse), bir düğümün en fazla k düğüme bağlanabileceği bağımsız küme, alt çizgelerle ilgilenen kusurlu tam boyama problemi de ele alınmıştır. ck(m) parametresi n düğümlü bütün çizgelerin k-kusurlu olarak en fazla m renkle tam boyanabileceği en büyük n sayısını vermektedir. Bu çalışmada şu sonuçlar elde edilmiştir: c0(4)=12, c1(3)=12 ve c2(2)=10. Ayrıca ck(m) parametresi için alt ve üst sınırlar veren bir formül geliştirildi.